#include "peru.h"
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
#include <random>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<ll,int>
#define cp complex<double>
#define vi vector<int>
#define ull unsigned long long
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
using namespace std;
ll f[2500002];
int q[2500002],l,r,a[2500002],L,R;
pii Q[2500002];
namespace T{
	ll v[2500002],l,r,mid,suf[2500002],pre[2500002];
	inline void clr(){
		l=1,r=0,mid=0;
		pre[0]=suf[1]=1e18;
	}
	inline void rebuild(){
		mid=(l+r)>>1;
		pre[mid]=suf[mid+1]=1e18;
		UF(i,mid,l)suf[i]=min(suf[i+1],v[i]);
		F(i,mid+1,r)pre[i]=min(pre[i-1],v[i]);
	}
	inline void eral(){
		++l;
		if(l>mid+1)rebuild();
	}
	inline void erar(){
		--r;
		if(r<mid)rebuild();
	}
	inline void push(ll w){
		v[++r]=w;
		pre[r]=min(pre[r-1],w);
	}
	inline ll query(){
		return min(suf[l],pre[r]);
	}
}
int solve(int n, int k, int* v){
	T::clr();
	F(i,1,n)a[i]=v[i-1];
	l=1,r=0;
	F(i,1,n){
		while(l<=r&&i-q[l]>=k){
			++l;
		}
		while(L<=R&&i-Q[L].second>=k){
			++L;T::eral();
		}
		while(l<=r&&a[q[r]]<a[i]){
			--r;
		}
		if(l>r)L=R+1,T::clr();
		else{
			while(L<=R&&Q[R].second>=q[r])--R,T::erar();
			pii w=make_pair(f[q[r]]+a[i],q[r]);
		//	while(L<=R&&w<=Q[R])--R;
			Q[++R]=w;T::push(w.first);
		}
		q[++r]=i;
		if(L<=R)f[i]=min(f[max(0,i-k)]+a[q[l]],T::query());
		else f[i]=f[max(0,i-k)]+a[q[l]];
	}
	int ans=0;
	F(i,1,n){
		ans=(ans*23ll+f[i])%1000000007;
	//	cerr<<f[i]<<" \n"[i==n];
	}
    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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~