#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
//#include "grader.cpp"
#include "peru.h"
typedef long long ll;
const int N=2500005,mod=(1e9)+7;
struct SegTree{
    ll tree[1<<23][2],sz;
    #define val(p) tree[p][0]
    #define lazy(p) tree[p][1]
    void init(int n){
        sz=1;
        while(sz<n)sz*=2;
    }
    void push(int p){
        if(lazy(p)){
            for(auto ch:{p*2+1,p*2+2}){
                lazy(ch)+=lazy(p);
                val(ch)+=lazy(p);
            }
            lazy(p)=0;
        }
    }
    void update(int l,int r,int p,int l_q,int r_q,ll val){
        if(l_q<=l&&r<=r_q){
            lazy(p)+=val;
            val(p)+=val;
            return;
        }
        push(p);
        int md=(l+r)>>1;
        if(l_q<=md)update(l,md,p*2+1,l_q,r_q,val);
        if(md<r_q)update(md+1,r,p*2+2,l_q,r_q,val);
        val(p)=max(val(p*2+1),val(p*2+2));
    }
    void update(int l,int r,ll val){
        update(0,sz-1,0,l,r,val);
    }
    ll query(int l,int r,int p,int l_q,int r_q){
        if(l_q<=l&&r<=r_q)return val(p);
        push(p);
        int md=(l+r)>>1;
        if(r_q<=md)return query(l,md,p*2+1,l_q,r_q);
        else if(md<l_q)return query(md+1,r,p*2+2,l_q,r_q);
        else return max(query(l,md,p*2+1,l_q,r_q),query(md+1,r,p*2+2,l_q,r_q));
    }
    ll query(int l,int r){
        return query(0,sz-1,0,l,r);
    }
}tree;
ll dp[N];
int solve(int n, int k, int* v){
    dp[0]=0;
    tree.init(n+1);
    for(int i=0;i<n;i++)tree.update(i+1,i+1,v[i]);
    deque<int>opt={0};
    for(int i=1;i<=n;i++){
        if(opt[0]<i-k)opt[0]++;
        if(opt.size()>1&&opt[0]==opt[1])opt.pop_front();
        int sz=opt.size();
        while(opt.size()>1&&dp[opt[sz-2]]+tree.query(opt[sz-2]+1,i)<dp[opt[sz-1]]+tree.query(opt[sz-1]+1,i))opt.pop_back(),sz--;
        dp[i]=dp[opt[sz-1]]+tree.query(opt[sz-1]+1,i);
        opt.push_back(i);
    }
    long long res=0;
    for(int i=1;i<=n;i++)res=(res*23+dp[i])%mod;
    return res;
}

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