#include<bits/stdc++.h>
#include"peru.h"

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

struct node{
	ll x;
	int l,r;
	node(ll x=0,int l=0,int r=0):x(x),l(l),r(r){}
	bool operator==(const node c)const{return x==c.x&&r==c.r;}
	bool operator<(const node c)const{return x==c.x?r<c.r:x>c.x;}
}q[2500005];

const int cys=1000000007;
int top;
int a[2500005],stk[2500005];
ll d[2500005];
priority_queue<node> q1,q2;

int solve(int n,int k,int *S){
	for(int i=0;i<n;i++) a[i+1]=S[i];
	d[0]=0;
	int cur=0,front=0,rear=0;
	for(int i=1;i<=n;i++){
		// cout<<"################ "<<i<<endl;
		while(top&&a[stk[top]]<a[i]){
			if(stk[top-1]>=i-k-1){
				// cout<<"erase "<<stk[top-1]<<' '<<stk[top]<<' '<<d[stk[top-1]]+a[stk[top]]<<endl;
				// q2.push(node(d[stk[top-1]]+a[stk[top]],stk[top-1],stk[top]));
				if(front<rear&&q[rear-1].l==stk[top-1]) rear--;
			}
			top--;
		}
		// cout<<"insert "<<stk[top]<<' '<<i<<' '<<d[stk[top]]+a[i]<<endl;
		// q1.push(node(d[stk[top]]+a[i],stk[top],i));
		node th(d[stk[top]]+a[i],stk[top],i);
		if(front<rear&&q[rear-1].l==stk[top]) rear--;
		while(front<rear&&q[rear-1].x>=th.x) rear--;
		q[rear++]=th;
		stk[++top]=i;
		// while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top()) q1.pop(),q2.pop();
		d[i]=1ll<<60;
		// while(!q1.empty()&&q1.top().l<i-k){
		// 	q1.pop();
		// 	while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top()) q1.pop(),q2.pop();
		// }
		while(front<rear&&q[front].l<i-k) front++;
		if(front<rear) chkmin(d[i],q[front].x);
		// if(!q1.empty()) chkmin(d[i],q1.top().x);
		// if(front<rear) cout<<"test "<<q[front].l<<' '<<q[front].r<<' '<<q[front].x<<endl;
		chkmin(cur,top);
		while(stk[cur]<=i-k) cur++;
		if(i>=k) chkmin(d[i],d[i-k]+a[stk[cur]]);
	}
	// for(int i=1;i<=n;i++) cout<<d[i]<<' ';
	// cout<<endl;
	ll ret=0;
	for(int i=1;i<=n;i++) ret=(ret*23+d[i])%cys;
	return ret;
}

implementer.cpp: In function ‘int main()’:
implementer.cpp:34:13: error: ‘fout’ was not declared in this scope; did you mean ‘out’?
   34 |     fprintf(fout, "%d\n", sol);
      |             ^~~~
      |             out
implementer.cpp: In function ‘char nextch()’:
implementer.cpp:15:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |     if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~