# include "peru.h"
# include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int mod=1e9+7,INF=2e9+1;
constexpr ll INFll=1e18;
int a[2500010],lc[2500010],rc[2500010];
ll f[2500010];
void chkmin(ll &x,const ll &y){x=min(x,y);}
ll slv(int rt,int l,int r,ll mn)
{
	if(l==r) return chkmin(f[l],mn),f[l];
	ll L=slv(lc[rt],l,rt-1,mn);
	chkmin(mn,L+a[rt]);
	ll R=slv(rc[rt],rt,r,mn);
	return min(L,R);
}
int solve(int n,int K,int *S)
{
	move(S,S+n,a+1);
	f[0]=0;
	fill(f+1,f+n+1,INFll);
	for(int l=0;l<=n;l+=K)
	{
		int r=min(l+K-1,n);
		if(l)
		{
			static int mx1[2500010],mx2[2500010],L[2500010],R[2500010];
			static ll minn[2500010];
			mx1[l]=mx2[l-1]=0;
			for(int i=l-1;i>=l-K;i--) mx1[i]=max(mx1[i+1],a[i]);
			for(int i=l;i<=r;i++) mx2[i]=max(mx2[i-1],a[i]);
			minn[l]=INFll;
			for(int i=l-1;i>=l-K;i--) minn[i]=min(minn[i+1],f[i]);
			for(int i=l,j=l-1;i<=r;i++)
			{
				while(j>=l-K && mx1[j]<=mx2[i]) j--;
				chkmin(f[i],minn[max(j,i-K)]+mx2[i]);
				L[i]=i-K;R[i]=j-1;
			}
			int p=r;
			while(p>=l && L[p]>R[p]) p--;
			if(p>=l)
			{
				int le=R[p]+1,ri=R[p];
				ll mn=INFll;
				for(int i=p;i>=l;i--)
				{
					while(le>L[i]) le--,chkmin(mn,f[le]+mx1[le+1]);
					while(ri<R[i]) ri++,chkmin(mn,f[ri]+mx1[ri+1]);
					chkmin(f[i],mn);
				}
			}
		}
		if(l<r)
		{
			int tp=0;
			static int stk[2500010];
			for(int i=l+1;i<=r;i++)
			{
				for(;tp && a[stk[tp]]<=a[i];tp--) lc[i]=stk[tp];
				if(tp) rc[stk[tp]]=i;
				stk[++tp]=i;
			}
			slv(stk[1],l,r,INFll);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=(ans*23ll+f[i])%mod;
	return ans;
}

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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~