#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define pb push_back
#define F first
#define S second
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
typedef vector<ll> vl;
typedef vector<vl> vvl;
vl v;
vvl stdata(6000);
ll sufix = 0;
struct Node{
Node *lnode, *rnode;
ll l, r, val = 0, pref = 0, suf = 0;
bool cover = 0;
Node(ll l, ll r) : l(l), r(r){
if(r-l==1) val=pref=suf=cover=v[l];
else{
ll mid =(r+l) / 2;
lnode = new Node(l, mid);
rnode = new Node(mid, r);
val = max(lnode->val, rnode->val);
val = max(val, lnode->suf+rnode->pref);
pref = lnode->pref;
suf = rnode->suf;
cover=lnode->cover&rnode->cover;
if(lnode->cover)pref+=rnode->pref;
if(rnode->cover)suf+=lnode->suf;
}
}
ll query(ll lo, ll hi){
if(r <= lo || hi <= l) return 0;
if(r <= hi && lo <= l){
// deb2(l, r);
ll ans = max(val, sufix+pref);
if(cover)sufix+=suf;
else sufix = suf;
return ans;
}
return max(rnode->query(lo, hi), lnode->query(lo, hi));
}
};
ll curr = 0;
void Node2(ll l, ll r, ll index = 1){
while(stdata[curr].size()<=index) stdata[curr].pb(0);
if(r-l==1) stdata[curr][index]=v[l];
else{
ll mid =(r+l) / 2;
Node2(l, mid, index*2);
Node2(mid, r, index*2+1);
stdata[curr][index] = stdata[curr][index*2]+stdata[curr][index*2+1];
}
}
ll query(ll lo, ll hi, ll l, ll r, ll index = 1){
if(r <= lo || hi <= l) return 0;
if(r <= hi && lo <= l){
return stdata[curr][index];
}
ll mid = (l+r) / 2;
return query(lo, hi, l, mid, index*2)+query(lo, hi, mid, r, index*2+1);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int q = L.size();
ll n = H.size();
vl C;
if(n>5000||q>5000){
fo(i, n) v.pb(H[i] == 1);
Node st(0, n+1);
fo(i, q){
sufix = 0;
// deb(i);
// deb(st.query(L[i], R[i]+1));
C.pb((R[i]-L[i]+1)*2-st.query(L[i], R[i]+1));
}
}else{
fo(meet, n){
v.assign(n, 0);
ll hi = H[meet];
for(ll i = meet; i>=0; i--){
hi = max(hi, (ll)H[i]);
v[i] = hi;
}
hi = H[meet];
for(ll i = meet; i<n; i++){
hi = max(hi, (ll)H[i]);
v[i] = hi;
}
// deb(meet);
// fo(i, n) deb(v[i]);
curr = meet;
Node2(0, n);
}
fo(ind, q){
ll best = 1e18;
for(ll meet = L[ind]; meet<=R[ind]; meet++){
curr = meet;
best = min(best, query(L[ind], R[ind]+1, 0, n));
}
C.pb(best);
}
}
// fo(i, q) deb(C[i]);
return C;
}
// int main(){
// // vector<int> a = {1, 1, 2, 1, 1, 1, 2, 2, 1};
// // vector<int> b = {0, 2};
// // vector<int> c = {5, 5};
// vector<int> a = {2, 4, 3, 5};
// vector<int> b = {0, 1};
// vector<int> c = {2, 3};
// minimum_costs(a, b, c);
// return 0;
// }
