#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long INF = 1e18;
long long a[2500005];
long long dp[2500005];
long long getmax(int le, int ri)
{
long long mxm=0;
for(int i=le;i<=ri;i++)
mxm = max(mxm, a[i]);
return mxm;
}
multiset<long long> s;
int solve(int n, int k, int* v)
{
a[0]=2e9+2;
deque<pair<long long,long long>> dq;///{poz,mxm}
dq.push_back({0,0});
s.insert(0);
for(int i=1;i<=n;i++)
{
a[i]=v[i-1];
dp[i]=INF;
dp[i] = min(dp[i], dp[max(0,i-k)]+getmax(max(0,i-k)+1,i));
while(!dq.empty() && dq.front().first < i-k)
{
s.erase(s.find(dp[dq.front().first]+dq.front().second));
dq.pop_front();
}
int ult=-1;
while(!dq.empty() && a[i] > dq.back().second)
{
ult = dq.back().first;
s.erase(s.find(dp[dq.back().first]+dq.back().second));
dq.pop_back();
}
if(ult!=-1)
{
dq.push_back({ult,a[i]});
s.insert(dp[ult]+a[i]);
}
if(!s.empty()) dp[i] = min(dp[i], *s.begin());
dq.push_back({i,0});
s.insert(dp[i]);
}
long long rez=0,put23=1;
for(int i=n;i>0;i--)
{
rez = (rez + dp[i]%MOD*put23)%MOD;
put23 = put23*23LL%MOD;
}
return rez;
}
/*
8 3
3 2 9 8 7 11 3 4
*/
