//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")
//Andrusha Holod did not qualify to IOI 2025 )))
//Hope Andrusha Holod will win IOI 2026
#include "peru.h"
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < ll, ull > piu;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;
const ll DIM = 100007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;
const ll dx[5] = { -1, -1, 0, 1, 0 };
const ll dy[5] = { -1, 0, -1, 0, 1 };
FILE* stream;
class segmentTree {
public:
void init(ll sz_) {
sz = sz_;
T.resize(4 * sz + 4);
build(0, 0, sz - 1);
}
ll queryMi(ll L, ll R) {
return queryMi(0, 0, sz - 1, L, R);
}
void updateF(ll pos, ll val) {
updateF(0, 0, sz - 1, pos, val);
}
void updateMx(ll L, ll R, ll val) {
if (L > R) return;
updateMx(0, 0, sz - 1, L, R, val);
}
private:
struct node {
ll mi, miF, mod;
};
ll sz;
vector < node > T;
void build(ll v, ll tl, ll tr) {
if (tl == tr) {
T[v] = { INF, INF, 0 };
return;
}
ll tm = (tl + tr) / 2;
build(2 * v + 1, tl, tm);
build(2 * v + 2, tm + 1, tr);
T[v].miF = min(T[2 * v + 1].miF, T[2 * v + 2].miF);
T[v].mi = min(T[2 * v + 1].mi, T[2 * v + 2].mi);
T[v].mod = 0;
}
void push(ll v) {
if (T[v].mod == 0) return;
T[2 * v + 1].mod = T[v].mod;
T[2 * v + 1].mi = T[2 * v + 1].miF + T[v].mod;
T[2 * v + 2].mod = T[v].mod;
T[2 * v + 2].mi = T[2 * v + 2].miF + T[v].mod;
T[v].mod = 0;
}
ll queryMi(ll v, ll tl, ll tr, ll L, ll R) {
if (tl > R || tr < L) return INF;
if (L <= tl && tr <= R) {
return T[v].mi;
}
push(v);
ll tm = (tl + tr) / 2;
return min(queryMi(2 * v + 1, tl, tm, L, R), queryMi(2 * v + 2, tm + 1, tr, L, R));
}
void updateF(ll v, ll tl, ll tr, ll pos, ll val) {
if (tl > pos || tr < pos) return;
if (tl == tr) {
T[v].miF = val;
T[v].mi = T[v].mod + val;
return;
}
push(v);
ll tm = (tl + tr) / 2;
updateF(2 * v + 1, tl, tm, pos, val);
updateF(2 * v + 2, tm + 1, tr, pos, val);
T[v].miF = min(T[2 * v + 1].miF, T[2 * v + 2].miF);
T[v].mi = min(T[2 * v + 1].mi, T[2 * v + 2].mi);
}
void updateMx(ll v, ll tl, ll tr, ll L, ll R, ll val) {
if (tl > R || tr < L) return;
if (L <= tl && tr <= R) {
T[v].mi = T[v].miF + val;
T[v].mod = val;
return;
}
push(v);
ll tm = (tl + tr) / 2;
updateMx(2 * v + 1, tl, tm, L, R, val);
updateMx(2 * v + 2, tm + 1, tr, L, R, val);
T[v].mi = min(T[2 * v + 1].mi, T[2 * v + 2].mi);
}
};
int n, k;
int solve(int N, int K, int* S) {
n = N;
k = K;
vector < ll > F(n);
ll mx = -INF;
segmentTree t;
t.init(n + 7);
for (int i = 0; i < k; i++) {
mx = max((ll)S[i], mx);
F[i] = mx;
t.updateF(i, F[i]);
}
mx = 0;
for (int i = k - 1; i >= 0; i--) {
t.updateMx(i, i, mx);
mx = max(mx, (ll)S[i]);
}
vector < ll > GreatL(n);
stack < pii > s;
for (int i = 0; i < n; i++) {
while (!s.empty() && s.top().first <= S[i]) s.pop();
if (s.empty()) GreatL[i] = -1;
else GreatL[i] = s.top().second;
s.push({ S[i], i });
}
for (int i = k; i < n; i++) {
t.updateMx(GreatL[i], i - 1, S[i]);
F[i] = t.queryMi(i - k, i - 1);
t.updateF(i, F[i]);
}
vector < ll > powers(n);
powers[0] = 1;
for (int i = 1; i < n; i++) powers[i] = (powers[i - 1] * 23) % mod;
ll res = 0;
for (int i = 0; i < n; i++) {
res += ( F[i] % mod ) * powers[n - 1 - i];
res %= mod;
}
return res;
}
/*
5 4
8 9 10 11 3
*/
