#include<bits/stdc++.h>
#include "peru.h"
#define f(i,x,y) for(int i=x;i<=y;i++)
#define df(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
const ll N=2.5e6+9,I=1e18,P=1e9+7;
ll n,a[N],x,k,y,z[N],zl,p[N],pl,f[N],fp[N],sz[N],sp[N],fl;
int as;
void rb(ll fg)
{
	fl=0;
	df(i,zl,1)fp[++fl]=z[i];
	f(i,1,pl)fp[++fl]=p[i];
	zl=(fl+fg)/2,pl=fl-zl;
	df(i,pl,1)p[i]=fp[fl--];
	z[1]=n+1;f(i,1,zl)z[i]=fp[fl--];
	p[0]=z[1];
	f(i,1,pl)sp[i]=min(f[p[i-1]]+a[p[i]],sp[i-1]);
	f(i,2,zl)sz[i]=min(f[z[i]]+a[z[i-1]],sz[i-1]);
}
int solve(int N,int K,int *S)
{
	n=N,k=K;
	f(i,1,n)a[i]=S[i-1];
	pl=zl=0;sz[0]=sz[1]=sp[0]=a[0]=f[n+1]=I;
	as=0;
	f(i,1,n)
	{
		if(pl+zl)
		{
			if(!zl||pl+zl==2)rb(2);
			if(z[zl]+k<i)--zl;
		}
		while(pl+zl)
		{
			if(!pl)rb(0);
			if(a[p[pl]]<=a[i])--pl;//cout<<p[pl],
			else break;
		}
//		df(i,zl,1)cout<<z[i];f(i,1,pl)cout<<p[i];
		p[++pl]=i;
		if(pl+zl!=1)sp[pl]=min(f[p[pl-1]]+a[i],sp[pl-1]);else sp[pl]=I;
		f[i]=min(sz[zl],sp[pl]);//cout<<pl;
		if(zl)f[i]=min(f[max(i-k,0ll)]+a[z[zl]],f[i]);
		else f[i]=min(f[max(i-k,0ll)]+a[p[1]],f[i]);
		as=(as*23ll+f[i])%P;//cout<<f[i]<<' ';
	}
	return as;
}