#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const long long INF = (long long)2e18 + 5;
long long n, q;
vector<long long> h, predp, sufdp, prenext, sufnext, ans;
vector<long long> minimum_costs(vector<int> H, vector<int> l, vector<int> r){
n = H.size(), q = l.size();
h = {0};
for(auto x : H) h.push_back(x);
predp.assign(n + 5, 0), sufdp.assign(n + 5, 0), prenext.assign(n + 5, 0), sufnext.assign(n + 5, 0), ans.assign(q, INF);
for(auto &x : l) x++;
for(auto &x : r) x++;
stack<pair<long long, long long>> stk;
stk.push({INF, -INF});
for(int i = 1; i <= n; i++){
while(stk.top().first <= h[i]) stk.pop();
prenext[i] = stk.top().second;
stk.push({h[i], i});
}
stk = {};
stk.push({INF, INF});
for(int i = n; i >= 1; i--){
while(stk.top().first <= h[i]) stk.pop();
sufnext[i] = stk.top().second;
stk.push({h[i], i});
}
if(n <= 5000 && q <= 5000){ // Subtask 1 & 2
for(int qq = 0; qq < q; qq++){
predp[l[qq] - 1] = sufdp[r[qq] + 1] = 0;
predp[l[qq]] = h[l[qq]];
for(int i = l[qq] + 1; i <= r[qq]; i++){
if(h[i] <= h[i - 1]) predp[i] = predp[i - 1] + h[i];
else{
int prv = max(prenext[i], (long long)l[qq] - 1);
predp[i] = predp[prv] + 1ll * (i - prv) * h[i];
}
}
sufdp[r[qq]] = h[r[qq]];
for(int i = r[qq] - 1; i >= l[qq]; i--){
if(h[i] <= h[i + 1]) sufdp[i] = sufdp[i + 1] + h[i];
else{
int prv = min(sufnext[i], (long long)r[qq] + 1);
sufdp[i] = sufdp[prv] + 1ll * (prv - i) * h[i];
}
}
for(int i = l[qq]; i <= r[qq]; i++) ans[qq] = min(ans[qq], predp[i] + sufdp[i] - h[i]);
}
}
return ans;
}
