#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 25e5, mod = 1e9 + 7;
const ll inf = 1e17;
ll seg[M*2],val[M*2],dp[M];
int n;
int power(int a,int b)
{
int ans=1;
for (;b;b>>=1,a=1ll*a*a%mod)
if (b&1) ans=1ll*ans*a%mod;
return ans;
}
void modify(int l,int r,ll x,int v=0,int s=0,int e=n)
{
if (l>=e or r<=s) return;
if (l<=s && e<=r)
{
val[v]+=x;
return;
}
int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
modify(l,r,x,lc,s,mid);
modify(l,r,x,rc,mid,e);
seg[v]=min(seg[lc]+val[lc],seg[rc]+val[rc]);
}
int solve(int N,int k,int* a)
{
n=N;
for (int i=0;i<2*n;i++) seg[i]=inf;
int mx=0;
for (int i=0;i<k;i++)
mx=max(mx,a[i]),dp[i]=mx;
set<pair<int,int>> se;
se.insert({0,0});
for (int i=0;i<n;i++)
{
int prv=i+1;
while (!se.empty())
{
pair<int,int> p=*se.rbegin();
if (p.second>=a[i]) break;
modify(p.first,prv,a[i]-p.second);
prv=p.first;
se.erase(p);
}
if (i>=k)
{
modify(i-k,i-k+1,inf);
dp[i]=seg[0]+val[0];
}
if (i!=n-1)
modify(i+1,i+2,dp[i]-inf);
se.insert({prv,a[i]});
se.insert({i+1,0});
}
int inv=power(23,mod-2),val=1,ans=0;
for (int i=0;i<n-1;i++) val=1ll*val*23%mod;
for (int i=0;i<n;i++,val=1ll*val*inv%mod)
ans=(ans+dp[i]%mod*val%mod)%mod;
return ans;
}
