#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define vi vector<int>
#define fi first
#define se second
#define local
#ifndef local
#include "meetings.h"
#endif
using namespace std;
const int N = 1e5+5;
int Q,n;
ll DD[5005][5005];
pair<int,pair<int,int> > t[4*N];
int F[N][2];
void build(int v,int tl,int tr,vi& H) {
if (tl == tr) {
int s = (H[tl] == 1);
t[v] = {s,{s,s} };
return;
}
int tm = (tl + tr)/2;
build(v*2,tl,tm,H);
build(v*2+1,tm+1,tr,H);
t[v].fi = max({t[v*2].fi,t[v*2+1].fi,t[v*2].se.se + t[v*2+1].se.fi});
t[v].se.fi = t[v*2].se.fi;
if (t[v*2].se.fi == tm - tl + 1) t[v].se.fi += t[v*2+1].se.fi;
t[v].se.se = t[v*2+1].se.se;
if (t[v*2+1].se.se == tr - tm) t[v].se.se += t[v*2].se.se;
}
pair<int,pair<int,int> > get(int v,int tl,int tr,int l,int r) {
if (r < tl || l > tr) return{0,{0,0}};
if (l <= tl && r >= tr) {
return {t[v].fi,{t[v].se.fi,t[v].se.se}};
}
int tm = (tl + tr)/2;
auto x1 = get(v*2,tl,tm,l,r);
auto x2 = get(v*2+1,tm+1,tr,l,r);
pair<int,pair<int,int> > x;
x.fi = max({x1.fi,x2.fi,x1.se.se + x2.se.fi});
x.se.fi = x1.se.fi;
if (x1.se.fi == tm - tl + 1) x.se.fi += x2.se.fi;
x.se.se = x2.se.se;
if (x2.se.se == tr - tm) x.se.se += x1.se.se;
return x;
}
vector<ll> small(vi H,vi L,vi R) {
vector<ll> T(Q);
vector<int> e = H,WW(n);
sort(e.begin(),e.end());
map<int,int> mp;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || e[i-1] != e[i]) {
mp[e[i]] = cnt;
WW[cnt] = e[i];
cnt++;
}
}
for (int i = 0; i < n; i++) {
int val = 0;
ll sum = 0;
for (int j = i; j >= 0; j--) {
val = max(val,H[j]);
sum += val;
DD[i][j] = sum;
}
sum = 0; val = 0;
for (int j = i; j < n; j++) {
val = max(val,H[j]);
sum += val;
DD[i][j] = sum;
}
}
for (int i = 0; i < Q; i++) {
int l = L[i], r = R[i];
ll ans = LLONG_MAX;
for (int x = l ; x <= r; x++) {
ll sum = DD[x][r] + DD[x][l] - H[x];
ans = min(ans,sum);
}
T[i] = ans;
}
return T;
}
vector<ll> case2(vi H,vi L,vi R) {
stack<int> s;
vector<ll> T(Q);
build(1,0,n-1,H);
for (int i = 0; i < n; i++) {
while (!s.empty() && H[s.top()] <= H[i]) s.pop();
F[i][0] = (s.size() ? s.top() : i);
s.push(i);
}
while(!s.empty()) s.pop();
for (int i = n-1; i >= 0; i--) {
while (!s.empty() && H[s.top()] <= H[i]) s.pop();
F[i][1] = (s.size() ? s.top() : i);
s.push(i);
}
for (int i = 0; i < Q;i ++) {
int l = L[i], r = R[i];
T[i] = 2*(r - l + 1) - get(1,0,n-1,l,r).fi;
}
return T;
}
vector<ll> minimum_costs(vi H, vi L,vi R) {
n = H.size(); Q = L.size();
if (n <= 5000 && Q <= 5000) return small(H,L,R);
return case2(H,L,R);
std::vector<long long> C(Q);
for (int j = 0; j < Q; ++j) {
C[j] = H[L[j]];
}
}
