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

#ifndef EVAL
#include "grader.cpp"
#endif

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::stack<ll> minL, idxL, valL, minR, idxR, valR;
    REP(i,1,n){
        while(!minL.empty() || !minR.empty()){
            if(minR.empty()){
                ll sz = minL.size();
                std::stack<ll> m_idx, m_val;
                rep(_,0,sz/2){
                    m_idx.push(idxL.top()); idxL.pop();
                    m_val.push(valL.top()); valL.pop();
                    minL.pop();
                }
                ll min = inf;
                while(!minL.empty()){
                    min = std::min(min, valL.top());
                    minR.push(min);
                    idxR.push(idxL.top());
                    valR.push(valL.top());
                    idxL.pop();
                    valL.pop();
                    minL.pop();
                }
                min = inf;
                while(!m_idx.empty()){
                    min = std::min(min, m_val.top());
                    minL.push(min);
                    idxL.push(m_idx.top());
                    valL.push(m_val.top());
                    m_idx.pop();
                    m_val.pop();
                }
            }
            if(v[idxR.top()] > v[i-1]) break;
            idxR.pop();
            valR.pop();
            minR.pop();
        }

        if(minR.empty()){
            ll sz = minL.size();
            std::stack<ll> m_idx, m_val;
            rep(_,0,sz/2){
                m_idx.push(idxL.top()); idxL.pop();
                m_val.push(valL.top()); valL.pop();
                minL.pop();
            }
            ll min = inf;
            while(!minL.empty()){
                min = std::min(min, valL.top());
                minR.push(min);
                idxR.push(idxL.top());
                valR.push(valL.top());
                idxL.pop();
                valL.pop();
                minL.pop();
            }
            min = inf;
            while(!m_idx.empty()){
                min = std::min(min, m_val.top());
                minL.push(min);
                idxL.push(m_idx.top());
                valL.push(m_val.top());
                m_idx.pop();
                m_val.pop();
            }
        }

        if(minR.empty()){
            minR.push(inf);
            valR.push(inf);
            idxR.push(i-1);
        }
        else{
            ll val = dp[idxR.top()+1]+v[i-1];
            idxR.push(i-1);
            valR.push(val);
            val = std::min(val, minR.top());
            minR.push(val);
        }

        if(minL.empty()){
            ll sz = minR.size();
            std::stack<ll> m_idx, m_val;
            rep(_,0,sz/2){
                m_idx.push(idxR.top()); idxR.pop();
                m_val.push(valR.top()); valR.pop();
                minR.pop();
            }
            ll min = inf;
            while(!minR.empty()){
                min = std::min(min, valR.top());
                minL.push(min);
                idxL.push(idxR.top());
                valL.push(valR.top());
                idxR.pop();
                valR.pop();
                minR.pop();
            }
            min = inf;
            while(!m_idx.empty()){
                min = std::min(min, m_val.top());
                minR.push(min);
                idxR.push(m_idx.top());
                valR.push(m_val.top());
                m_idx.pop();
                m_val.pop();
            }
        }

        if(idxL.top() < i-k){
            idxL.pop();
            minL.pop();
            valL.pop();
        }

        if(minL.empty()){
            ll sz = minR.size();
            std::stack<ll> m_idx, m_val;
            rep(_,0,sz/2){
                m_idx.push(idxR.top()); idxR.pop();
                m_val.push(valR.top()); valR.pop();
                minR.pop();
            }
            ll min = inf;
            while(!minR.empty()){
                min = std::min(min, valR.top());
                minL.push(min);
                idxL.push(idxR.top());
                valL.push(valR.top());
                idxR.pop();
                valR.pop();
                minR.pop();
            }
            min = inf;
            while(!m_idx.empty()){
                min = std::min(min, m_val.top());
                minR.push(min);
                idxR.push(m_idx.top());
                valR.push(m_val.top());
                m_idx.pop();
                m_val.pop();
            }
        }
        
        dp[i] = dp[std::max(0ll, i-k)]+v[idxL.top()];
        if(!valL.empty()) dp[i] = std::min(dp[i], minL.top());
        if(!valR.empty()) dp[i] = std::min(dp[i], minR.top());
    }
    ll ret = 0;
    rep(i,0,n){
        ret = ret*mul+dp[i+1];
        ret %= mod;
    }
    return ret;
}

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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
answer.code:5:10: fatal error: grader.cpp: No such file or directory
    5 | #include "grader.cpp"
      |          ^~~~~~~~~~~~
compilation terminated.