#include "peru.h"
#include <set>
#include <deque>
#define magic_sauce inline __attribute__((always_inline))
using ll = long long;
const ll INF = 1e18;
const int MOD = 1e9 + 7;
magic_sauce ll min( ll a, ll b ){ return a < b ? a : b; }
magic_sauce ll max( ll a, ll b ){ return a > b ? a : b; }
int ans_hash( int n, ll v[] ){
int ret = 0;
for( int i = 0 ; i < n ; i++ )
ret = (ret * 23LL + v[i]) % MOD;
return ret;
}
/*
ans[i] = min{ ans[max{ i - k, prev_bigger( x ) }] + x | x=v[i]..+INF }
// echivalent:
ans[i] = min{ ans[j] + max{ v[j+1..i] } | j=i-k..i-1 }
// folosim stiva de maxime partiale
// ans este crescator => daca avem un interval [st, dr] de maxime partiale egale atunci clar alegem pe st
// daca x[0..k-1] sunt pozitiile din stiva
// atunci are sens sa luam doar o pozitie de tipul x[i] + 1
// obs: santinela x[-1] = i-k
// tinem pozitiile de acest tip intr-un multiset
*/
int solve( int n, int k, int *v ){
ll *ans = new ll[n];
std::multiset<ll> samples;
std::deque<int> stack;
for( int i = 0 ; i < k ; i++ ){
while( !stack.empty() && v[stack.back()] < v[i] )
stack.pop_back();
stack.push_back( i );
ans[i] = v[stack.front()];
}
// sample stack succesors
for( int i = 0 ; i + 1 < (int)stack.size() ; i++ )
samples.insert( ans[stack[i]] + v[stack[i + 1]] );
samples.insert( +INF ); // santinela
for( int i = k ; i < n ; i++ ){
// adaugam v[i], scoatem v[i - k]
// push
while( !stack.empty() && v[stack.back()] < v[i] ){
int popped = stack.back();
stack.pop_back();
if( !stack.empty() )
samples.erase( samples.find( ans[stack.back()] + v[popped] ) );
}
if( !stack.empty() )
samples.insert( ans[stack.back()] + v[i] );
stack.push_back( i );
// pop
int j = i - k; // pentru convenienta
if( stack.front() == j ){
stack.pop_front();
if( !stack.empty() )
samples.erase( samples.find( ans[j] + v[stack.front()] ) );
}
ans[i] = min( ans[i - k] + v[stack.front()], *samples.begin() );
}
ll ret = ans_hash( n, ans );
delete []ans;
return ret;
}
