#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;
    std::deque<ll> slide_max;
    std::map<ll,ll> mem;
    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];
            dec(mem, val.back());
            idx.pop_back();
            val.pop_back();
            max.pop_back();
        }
        if(nID != -1){
            idx.pb(nID);
            val.pb(nval);
            max.pb(v[i-1]);
            mem[nval]++;
        }
        else{
            idx.pb(i-1);
            val.pb(v[i-1]+dp[i-1]);
            max.pb(v[i-1]);
            mem[v[i-1]+dp[i-1]]++;
        }
        if(!idx.empty() && idx[0] < i-k){
            assert(idx[0] == i-k-1);
            dec(mem, val[0]);
            idx.pop_front();
            val.pop_front();
            max.pop_front();
        }
        while(!slide_max.empty()){
            if(v[slide_max.back()] > v[i-1]) break;
            slide_max.pop_back();
        }
        slide_max.pb(i-1);
        if(slide_max[0] < i-k) slide_max.pop_front();

        dp[i] = dp[std::max(0ll, i-k)]+v[slide_max[0]];
        if(!val.empty()) dp[i] = std::min(dp[i], (*mem.begin()).first);
    }
    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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~