#include <bits/stdc++.h>
#include "peru.h"
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
 
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vll>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
 
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 3e6 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;
 
ll dp[MAXN];
stack<ll> l, r;
 
struct node{
	ll opt;
	int arr, ind;
	
	node(ll opt, int arr, int ind){
		this->opt = opt;
		this->arr = arr;
		this->ind = ind;
	}
};
 
deque<node> d;
 
int add(ll a, ll b){
	return (a + b) % mod;
}
 
int mul(ll a, ll b){
	return (a * b) % mod;
}
 
ll get_min(){
	ll ret = INF;
	if(!l.empty()) ret = min(ret, l.top());
	if(!r.empty()) ret = min(ret, r.top());
	return ret;
}
 
void push(stack<ll> &s, ll val){
	if(s.empty()) s.push(val);
	else s.push(min(val, s.top()));	
}
 
void rebuild(){
	while(!l.empty()) l.pop();
	while(!r.empty()) r.pop();
	int sz = d.size();
	int line = sz / 2;
	
	vector<node> v;
	REP(i, line) v.PB(d.front()), d.PPF();
	while(!v.empty()){
		push(l, v.back().opt);
		d.PF(v.back());
		v.PPB();
	}
	
	REP(i, sz - line) v.PB(d.back()), d.PPB();
	while(!v.empty()){
		push(r, v.back().opt);
		d.PB(v.back());
		v.PPB();
	}
}
 
 
int solve(int n, int k, int *arr){
	int ret = 0;
	for(int i = 1; i <= n; i++){
		if(i == 1){
			dp[i] = arr[i - 1];
			d.PB(node(dp[i], arr[i - 1], i));
			push(r, arr[i - 1]);
			ret = add(mul(ret, 23), dp[i]);
			continue;
		}
		int dpind = i;
		while(!d.empty() and d.back().arr <= arr[i - 1]){
			dpind = d.back().ind;			
			d.PPB();
			if(r.empty()) rebuild();
			else r.pop();
		}
		
		d.PB(node(dp[dpind - 1] + arr[i - 1], arr[i - 1], dpind));
		push(r, dp[dpind - 1] + arr[i - 1]);
		
		if(i > k){
			ll arrmax = d.front().arr;
			
			d.pop_front();
			if(l.empty()) rebuild();
			else l.pop();
			
			if(d.empty()){
				d.push_front(node(dp[i - k] + arrmax, arrmax, i - k + 1));
				push(l, dp[i - k] + arrmax);
			}else if(d.front().ind > i - k + 1){
				d.push_front(node(dp[i - k] + arrmax, arrmax, i - k + 1));
				push(l, dp[i - k] + arrmax);
			}
			
		}
		dp[i] = get_min();
		ret = add(mul(ret, 23), dp[i]);
	}
	return ret;
}

implementer.cpp: In function ‘int main()’:
implementer.cpp:34:13: error: ‘fout’ was not declared in this scope; did you mean ‘out’?
   34 |     fprintf(fout, "%d\n", sol);
      |             ^~~~
      |             out
implementer.cpp: In function ‘char nextch()’:
implementer.cpp:15:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |     if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~