#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
template<class T> bool chmin(T& a, T b) { if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, T b) { if(a >= b) return 0; a = b; return 1; }

/*
 前から DP？それとも最大値分割？
 前から DP する. dp[最初の生存] = コストの最小値.
 dp は単調増加なので, dp[i-1] から更新できる位置を dp[i] から更新する必要はない.
 A[i] から, 「A[i] より先にある A[i] 以上の最初の要素」に辺を張り, これをたどりながら更新, すでに更新されていたら break して, dp[i+K] を更新
 
 1. A[i] から, 「A[i] より先にある A[i] 以上の最初の要素」に辺を張る (後ろから stack で管理)
 2. max(A[i:i+K]) をスライド最大値で計算
 3. DP する
 */
constexpr int MOD = 1000000007;
int solve(int N, int K, int* S) {
    vector<int> nxt = [&]{
        vector<int> nxt(N);
        vector<pair<int, int>> q;
        q.emplace_back(INT_MAX, N);
        for(int i = N; i--; ) {
            while(q.back().first <= S[i]) q.pop_back();
            nxt[i] = q.back().second;
            q.emplace_back(S[i], i);
        }
        return nxt;
    }();
    vector<ll> dp(N + 1, INF);
    dp[0] = 0;
    int last = 0;
    for(int i = 0; i < N; i++) {
        if(dp[i] == INF) continue;
        chmax(last, i);
        int j = i;
        while(j < N && j - i < K) {
            if(nxt[j] > i + K) {
                dp[i + K] = dp[i] + S[j];
            }
            const int k = min(nxt[j], i + K);
            if(chmin(dp[k], dp[i] + S[j])) {
                if(nxt[j] > i + K) break;
                chmax(last, k);
                j = k;
            }
            else j = last;
        }
    }
    for(int i = N; i--; ) chmin(dp[i], dp[i + 1]);
    
    ll ans = 0;
    for(int i = 1; i <= N; i++) {
        ans *= 23;
        ans += dp[i];
        ans %= MOD;
    }
    return ans;
}

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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~