#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const long long N = 1e5 + 5, INF = (long long)2e18 + 5;
long long n, q;
vector<long long> h, predp, sufdp, prenext, sufnext, ans;
struct Node{
int ans, pre, suf, len;
};
struct SegTree{
Node tree[N * 4];
Node merge(Node a, Node b){
Node c;
c.pre = a.pre;
if(a.pre == a.len) c.pre = a.len + b.pre;
c.suf = b.suf;
if(b.suf == b.len) c.suf = a.suf + b.len;
c.ans = max({a.ans, b.ans, c.pre, c.suf, a.suf + b.pre});
c.len = a.len + b.len;
// cout << a.ans << " " << a.pre << " " << a.suf << " " << a.len << "\n";
// cout << b.ans << " " << b.pre << " " << b.suf << " " << b.len << "\n";
// cout << c.ans << " " << c.pre << " " << c.suf << " " << c.len << "\n\n\n";
return c;
}
void build(int v = 1, int l = 1, int r = n){
if(l == r) tree[v] = {h[l] == 1, h[l] == 1, h[l] == 1, 1};
else{
int m = l + (r - l) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}
}
Node query(int l, int r, int v = 1, int tl = 1, int tr = n){
if(l > r) return {0, 0, 0, 0};
else if(l == tl && r == tr) return tree[v];
else{
int tm = tl + (tr - tl) / 2;
return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
}
}
};
SegTree sgt;
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]);
}
}
else{ // Subtask 3
sgt.build();
for(int qq = 0; qq < q; qq++){
ans[qq] = (r[qq] - l[qq] + 1) * 2 - sgt.query(l[qq], r[qq]).ans;
}
}
return ans;
}
