#include "peru.h"
#include "bits/stdc++.h"
namespace {
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
using i64 = long long;
constexpr i64 inf = i64(1E18);
constexpr int md = int(1E9) + 7;
struct mindeque {
std::vector<std::pair<i64, i64>> lhs;
std::vector<std::pair<i64, i64>> rhs;
void balance_l() {
int n = int(rhs.size());
std::vector<int> vv;
for (int k = 0; k < n / 2; ++k) {
vv.emplace_back(rhs.back().first);
rhs.pop_back();
}
for (int k = 0; k < (n + 1) / 2; ++k) {
emplace_front(rhs.back().first);
rhs.pop_back();
}
for (int k = 0; k < n / 2; ++k){
emplace_back(vv.back());
vv.pop_back();
}
}
void balance_r() {
int n = int(lhs.size());
std::vector<int> vv;
for (int k = 0; k < n / 2; ++k) {
vv.emplace_back(lhs.back().first);
lhs.pop_back();
}
for (int k = 0; k < (n + 1) / 2; ++k) {
emplace_back(lhs.back().first);
lhs.pop_back();
}
for (int k = 0; k < n / 2; ++k){
emplace_front(vv.back());
vv.pop_back();
}
}
void emplace_front(i64 x) {
lhs.emplace_back(x, std::min(lhs.empty() ? inf : lhs.back().second, x));
}
void emplace_back(i64 x) {
rhs.emplace_back(x, std::min(rhs.empty() ? inf : rhs.back().second, x));
}
void pop_back() {
if (rhs.empty()) {
balance_r();
}
rhs.pop_back();
}
void pop_front() {
if (lhs.empty()) {
balance_l();
}
lhs.pop_back();
}
i64 min() {
i64 res = inf;
if (!lhs.empty()) {
res = std::min(res, lhs.back().second);
}
if (!rhs.empty()) {
res = std::min(res, rhs.back().second);
}
return res;
}
};
};
int solve(int N, int K, int* A) {
std::vector<i64> f(N + 1, inf);
std::deque<int> deq;
f[0] = 0;
mindeque mindeq;
for (int i = 1; i <= N; ++i) {
if (!deq.empty() && deq.front() == i - K - 1) {
mindeq.pop_front();
deq.pop_front();
}
while (!deq.empty() && A[deq.back() - 1] <= A[i - 1]) {
mindeq.pop_back();
deq.pop_back();
}
if (!deq.empty()) {
mindeq.pop_back();
mindeq.emplace_back(f[deq.back()] + A[i - 1]);
}
deq.emplace_back(i);
debug(i, deq);
f[i] = mindeq.min();
f[i] = std::min(f[i], f[std::max(0, i - K)] + A[deq.front() - 1]);
mindeq.emplace_back(f[i]);
#ifdef LOCAL
int mx = 0;
i64 real = inf;
for (int j = i; j >= std::max(1, i - K + 1); --j) {
mx = std::max(mx, A[j - 1]);
real = std::min(real, f[j - 1] + mx);
}
mx = 0;
for (int j = i; j >= std::max(1, i - K + 1); --j) {
mx = std::max(mx, A[j - 1]);
real = std::min(real, f[j - 1] + mx);
if (real == f[j - 1] + mx) {
debug(i, j - 1);
}
}
debug(real, f[i]);
assert(real == f[i]);
#endif
}
int ans = 0;
for (int i = 0; i < N; ++i) {
int x = f[i + 1] % md;
debug(i, x);
ans = (ans * 23LL + x) % md;
}
return ans;
}
