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

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()

constexpr ll inf = (1ll<<60);
constexpr ll mod = 1e9+7;
constexpr ll mul = 23;

void dec(std::map<ll,ll> &mem, ll el){
    mem[el]--;
    if(mem[el] == 0) mem.erase(el);
}

int solve(int n, int k, int* v){
    vi dp(n+1, inf);
    dp[0] = 0;
    std::deque<ll> idx, val, max;
    idx.pb(0);
    val.pb(0);
    max.pb(0);
    REP(i,1,n){
        ll nID = -1, nval = -1;
        while(!idx.empty()){
            if(max.back() > v[i-1]) break;
            nID = idx.back();
            nval = val.back()-max.back()+v[i-1];
            idx.pop_back();
            val.pop_back();
            max.pop_back();
        }
        if(nID != -1){
            idx.pb(nID);
            val.pb(nval);
            max.pb(v[i-1]);
        }
        if(!idx.empty() && idx[0] < i-k){
            assert(idx[0] == i-k-1);
            nID = i-k;
            nval = dp[i-k]+max[0];
            ll nmax = max[0];
            if(idx.size() >= 2 && val[1] <= nval){
                idx.pop_front();
                val.pop_front();
                max.pop_front();
            }
            else{
                idx[0] = nID;
                val[0] = nval;
                max[0] = nmax;
            }
        }
        dp[i] = val[0];
        while(!idx.empty()){
            if(val.back() < dp[i]+v[i-1]) break;
            val.pop_back();
            idx.pop_back();
            max.pop_back();
        }
        val.pb(dp[i]+v[i-1]);
        idx.pb(i);
        max.pb(v[i-1]);
    }
    ll ret = 0;
    rep(i,0,n){
        ret = ret*mul+dp[i+1];
        ret %= mod;
    }
    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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~