#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
const int MAX = 2.5e6 + 5;
int N, K;
int A[MAX];
lint dp[MAX];
int left_geq[MAX];
int minqhead = 0;
int minqtail = 0;
pair<int, long long> minq[MAX];
int minstsz = 0;
int minst[MAX];
void InsertMinQueue(int p, long long x) {
while (minqhead < minqtail && minq[minqtail - 1].second >= x) {
minqtail--;
}
minq[minqtail++] = {p, x};
}
void PopQueue(int p) {
while (minqhead < minqtail && minq[minqhead].first < p) {
minqhead++;
}
}
int cost[MAX]; // cost[i] = maximum value in [i - K + 1, i]
int at_most[MAX]; // at_most[i] = farthest segment for current subtree
vector<int> adj[MAX]; // adjacency list
void Dfs(int u, lint alt_dp) { // subtrees form a contiguous segment, so when we DFS we visit them in order 0, 1, 2, ..
PopQueue(u - K);
dp[u] = min({alt_dp, dp[max(u - K, 0)] + cost[u], minqhead == minqtail ? INF : minq[minqhead].second});
reverse(begin(adj[u]), end(adj[u]));
assert(is_sorted(begin(adj[u]), end(adj[u])));
for (auto v : adj[u]) {
if (u + K < at_most[v]) {
InsertMinQueue(u, dp[u] + A[v]);
// Note that, nxt_v has distance > K to u, so dp[u] wouldn't exist anymore in minQueue
Dfs(v, alt_dp);
} else {
Dfs(v, min(alt_dp, dp[u] + A[v]));
}
}
}
int solve(int n, int k, int* v) {
N = n, K = k;
for (int i = 0; i < N; i++) {
A[i + 1] = v[i];
}
{ // Compute left_geq[i] = greatest j < i, s.t. V[j] >= V[i]
for (int i = 1; i <= N; i++) {
while (minstsz > 0 && A[minst[minstsz - 1]] < A[i]) {
minstsz--;
}
left_geq[i] = minstsz == 0 ? 0 : minst[minstsz - 1];
minst[minstsz++] = i;
}
minstsz = 0;
}
{ // Compute cost[i]
minq[minqtail++] = {0, 0}; // for maxQueue
for (int i = 1; i <= N; i++) {
while (minqhead < minqtail && minq[minqhead].first <= i - K) {
minqhead++;
}
while (minqhead < minqtail && minq[minqtail - 1].second <= A[i]) {
minqtail--;
}
minq[minqtail++] = {i, A[i]};
cost[i] = minq[minqhead].second;
}
minqhead = minqtail = 0;
}
for (int i = N; i >= 1; i--) {
int p = left_geq[i];
adj[p].emplace_back(i);
at_most[i] = max(at_most[i], i);
at_most[p] = max(at_most[p], at_most[i]);
}
Dfs(0, INF);
int ans = 0;
for (int i = 1; i <= N; i++) {
ans = (1ll * ans * 23 + dp[i]) % int(1e9 + 7);
}
return ans;
}
