#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;
#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
struct segtree {
struct node {
i64 ans = inf;
i64 lz = 0;
void modify(i64 x) {
ans += x;
lz += x;
}
};
node unite(const node lhs, const node rhs) {
node res;
res.ans = std::min(lhs.ans, rhs.ans);
return res;
}
int n;
std::vector<node> tree;
segtree(int n_) : n(n_), tree(n << 1) {}
void push(int v, int l, int r) {
def;
tree[lv].modify(tree[v].lz);
tree[rv].modify(tree[v].lz);
tree[v].lz = 0;
}
void set(int v, int l, int r, int p, i64 x) {
if (l == r) {
tree[v].ans = x;
return;
}
def;
push(v, l, r);
if (p <= mid) {
set(lv, l, mid, p, x);
} else {
set(rv, mid + 1, r, p, x);
}
tree[v] = unite(tree[lv], tree[rv]);
}
void set(int p, i64 x) {
set(0, 0, n - 1, p, x);
}
void modify(int v, int l, int r, int ql, int qr, int x) {
if (ql == l && r == qr) {
tree[v].modify(x);
return;
}
def;
if (qr <= mid) {
modify(lv, l, mid, ql, qr, x);
} else if (mid + 1 <= ql) {
modify(rv, mid + 1, r, ql, qr, x);
} else {
modify(lv, l, mid, ql, mid, x);
modify(rv, mid + 1, r, mid + 1, qr, x);
}
tree[v] = unite(tree[lv], tree[rv]);
}
void modify(int l, int r, int x) {
modify(0, 0, n - 1, l, r, x);
}
i64 get(int v, int l, int r, int ql, int qr) {
if (ql == l && r == qr) {
return tree[v].ans;
}
def;
push(v, l, r);
if (qr <= mid) {
return get(lv, l, mid, ql, qr);
} else if (mid + 1 <= ql) {
return get(rv, mid + 1, r, ql, qr);
} else {
return std::min(get(lv, l, mid, ql, mid), get(rv, mid + 1, r, mid + 1, qr));
}
}
i64 get(int l, int r) {
return get(0, 0, n - 1, l, r);
}
};
};
int solve(int N, int K, int* A){
std::vector<i64> f(N + 1, inf);
f[0] = 0;
// segtree seg(N + 1);
// seg.set(0, 0);
// std::vector<int> stk {-1};
std::vector<int> stk;
std::vector<int> prv(N);
for (int i = 0; i < N; ++i) {
while (!stk.empty() && A[stk.back()] <= A[i]) {
stk.pop_back();
}
prv[i] = stk.empty() ? -1 : stk.back();
stk.emplace_back(i);
}
debug(prv);
std::deque<int> deq;
for (int i = 1; i <= N; ++i) {
if (deq.front() == i - K - 1) {
deq.pop_front();
}
while (!deq.empty() && A[deq.back()] <= A[i - 1]) {
deq.pop_back();
}
auto eval = [&](int x) -> i64 {
return f[std::max(prv[x] + 1, i - K)] + A[x];
};
deq.emplace_back(i - 1);
int n = int(deq.size());
for (auto j : deq) {
debug(j, eval(j));
f[i] = std::min(f[i], eval(j));
}
#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;
}
