#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10;
const ll inf = 1e18, mod = 1e9 + 7;
ll a[maxn], dp[maxn], tree[4 * maxn], lazy[4 * maxn];
void push_lazy(int root, int left, int right)
{
tree[root] += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
lazy[root] = 0;
}
void update(int root, int left, int right, int pos, ll val)
{
push_lazy(root, left, right);
if (left == right)
{
tree[root] = val;
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
update(root * 2, left, mid, pos, val);
else
update(root * 2 + 1, mid + 1, right, pos, val);
tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}
ll query(int root, int left, int right, int qleft, int qright)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return inf;
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return min(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
void range_update(int root, int left, int right, int qleft, int qright, ll val)
{
///cout << root << " " << left << " " << right << endl;
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] += val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
range_update(root * 2, left, mid, qleft, qright, val);
range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}
int solve(int n, int k, int *S)
{
for (int i = 0; i < n; i ++)
a[i + 1] = S[i];
update(1, 0, n, 0, a[1]);
stack < int > st;
st.push(1);
for (int i = 1; i <= n; i ++)
{
///cout << "---------------- " << i << endl;
dp[i] = query(1, 0, n, max(0, i - k), i - 1);
update(1, 0, n, i, dp[i] + a[i + 1]);
if (i != n)
{
while(!st.empty() && a[st.top()] < a[i + 1])
{
int pos = st.top();
st.pop();
int from = 1;
if (!st.empty())
from = st.top() + 1;
///cout << from << " " << pos << endl;
range_update(1, 0, n, from - 1, pos - 1, a[i + 1] - a[pos]);
///cout << "finito" << endl;
}
}
st.push(i + 1);
/**ll mx = a[i];
for (int j = i - 1; j >= max(0, i - k); j --)
{
dp[i] = min(dp[i], dp[j] + mx);
mx = max(mx, a[j]);
}*/
}
/**for (int i = 1; i <= n; i ++)
cout << dp[i] << " ";
cout << endl;*/
ll cur = 1, ans = 0;
for (int i = n; i > 0; i --)
{
ans = (ans + (dp[i] % mod) * cur) % mod;
cur = (cur * (ll)23) % mod;
}
return ans;
}
