#include "peru.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


constexpr int MO = 1'000'000'007;
constexpr Int INF = 1001001001001001001LL;

struct Entry {
  int pos;
  Int val;
};
struct Deque {
  int lens[2];
  vector<pair<Entry, Int>> pss[3];
  Deque(int n) : lens{} {
    for (int h = 0; h < 3; ++h) {
      pss[h].assign(n + 1, make_pair(Entry{-1, INF}, INF));
    }
  }
  
  void push(int h, const Entry &e) {
    const Int mn = min(pss[h][lens[h]].second, e.val);
    pss[h][++lens[h]] = make_pair(e, mn);
  }
  // half of h^1 to h
  void reduce(int h) {
    assert(!lens[h]);
    const int sz = lens[h ^ 1];
    lens[h] = lens[h ^ 1] = 0;
    copy(pss[h ^ 1].begin() + 1, pss[h ^ 1].begin() + (sz + 1), pss[2].begin());
    for (int i = sz - sz/2; --i >= 0; ) {
      push(h, pss[2][i].first);
    }
    for (int i = sz - sz/2; i < sz; ++i) {
      push(h ^ 1, pss[2][i].first);
    }
  }
  
  int size() const {
    return lens[0] + lens[1];
  }
  Entry front() {
    if (!lens[0]) reduce(0);
    assert(lens[0]);
    return pss[0][lens[0]].first;
  }
  Entry back() {
    if (!lens[1]) reduce(1);
    assert(lens[1]);
    return pss[1][lens[1]].first;
  }
  void pushFront(const Entry &e) {
    push(0, e);
  }
  void pushBack(const Entry &e) {
    push(1, e);
  }
  void popFront() {
    if (!lens[0]) reduce(0);
    assert(lens[0]);
    --lens[0];
  }
  void popBack() {
    if (!lens[1]) reduce(1);
    assert(lens[1]);
    --lens[1];
  }
  Int getMin() const {
    Int mn = INF;
    for (int h = 0; h < 2; ++h) {
      chmin(mn, pss[h][lens[h]].second);
    }
    return mn;
  }
  friend ostream &operator<<(ostream &os, const Deque &que) {
    os << "[ ";
    for (int i = que.lens[0]; i >= 1; --i) {
      os << "(" << que.pss[0][i].first.pos << "," << que.pss[0][i].first.val << "; " << que.pss[0][i].second << ") ";
    }
    os << "| ";
    for (int i = 1; i <= que.lens[1]; ++i) {
      os << "(" << que.pss[1][i].first.pos << "," << que.pss[1][i].first.val << "; " << que.pss[1][i].second << ") ";
    }
    os << "]";
    return os;
  }
};

int solve(int N, int K, int *S) {
  vector<Int> dp(N + 1, INF);
  dp[0] = 0;
  Deque que(N);
  for (int i = 0; i < N; ++i) {
    for (; que.size() && S[que.back().pos] <= S[i]; que.popBack()) {}
    {
      Entry e;
      e.pos = i;
      e.val = dp[que.size() ? (que.back().pos + 1) : 0] + S[i];
      que.pushBack(e);
    }
    for (; que.front().pos < i + 1 - K; que.popFront()) {}
// cerr<<que<<endl;
    assert(que.size());
    {
      const Entry e = que.front();
      que.popFront();
      chmin(dp[i + 1], que.getMin());
      chmin(dp[i + 1], dp[max(i + 1 - K, 0)] + S[e.pos]);
      que.pushFront(e);
    }
  }
// cerr<<"dp = "<<dp<<endl;
  
  Int ans = 0;
  for (int i = 1; i <= N; ++i) {
    ans = (ans * 23 + dp[i]) % MO;
  }
  return ans;
}

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