#include "meetings.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=1e5+500;
const ll inf=1e18+900;
const ll mod=1e9+7;
vector<pii> vec;
ll rt[maxn];
ll seg[maxn*4];
void bild(ll l,ll r,ll node){
if(l+1==r){
seg[node]=rt[l];
return;
}
ll mid=(l+r)/2;
bild(l,mid,2*node);
bild(mid,r,2*node+1);
seg[node]=max(seg[2*node],seg[2*node+1]);
}
ll findMx(ll L,ll R,ll node,ll l,ll r){
if(l<=L && R<=r){
return seg[node];
}
if(r<=L || R<=l)return 0;
ll mid=(L+R)/2;
return max(findMx(L,mid,2*node,l,r),findMx(mid,R,2*node+1,l,r));
}
ll esht(pii a,pii b){
pii c=mp(max(a.F,b.F),min(a.S,b.S));
if(c.F<=c.S)return c.S-c.F+1;
return 0;
}
ll findAns(ll l,ll r){
ll x=lower_bound(vec.begin(),vec.end(),mp(l+1,(ll)0))-vec.begin()-1;
ll ans=0;
if(x>=0){
ans=max(ans,esht(vec[x],mp(l,r)));
}
ll y=lower_bound(vec.begin(),vec.end(),mp(r+1,(ll)0))-vec.begin()-1;
if(y>=0){
ans=max(ans,esht(vec[y],mp(l,r)));
}
ans=max(ans,findMx(0,vec.size(),1,x+1,y));
return ans;
}
vector<ll> solve(vector<int> h,vector<int> l,vector<int> r){
vector<ll> anS(l.size());
ll n=h.size();
ll q=l.size();
for(ll i=0;i<n;i++){
if(h[i]==1){
if(vec.empty()){
vec.pb(mp(i,i));
}else{
if(vec.back().S==i-1){
vec.back().S=i;
}else{
vec.pb(mp(i,i));
}
}
}
}
for(ll i=0;i<vec.size();i++){
rt[i]=vec[i].S-vec[i].F+1;
}
bild(0,vec.size(),1);
for(ll i=0;i<q;i++){
anS[i]=2*(r[i]-l[i]+1)-findAns(l[i],r[i]);
}
return anS;
}
ll tmp[maxn];
vector<ll> easy(vector<int> h,vector<int> l,vector<int> r){
vector<ll> anS(l.size());
ll n=h.size();
ll q=l.size();
for(ll i=0;i<q;i++){
stack<ll> stk;
stk.push(l[i]);
ll res=h[l[i]];
tmp[l[i]]=res;
for(ll j=l[i]+1;j<=r[i];j++){
res+=h[j];
while(stk.size() && h[stk.top()]<=h[j]){
ll v=stk.top();
stk.pop();
ll f;
if(stk.empty()){
f=l[i];
}else{
f=stk.top()+1;
}
res+=(h[j]-h[v])*(v-f+1);
}
stk.push(j);
tmp[j]=res;
}
while(stk.size())stk.pop();
stk.push(r[i]);
res=h[r[i]];
tmp[r[i]]+=res;
for(ll j=r[i]-1;j>=l[i];j--){
res+=h[j];
while(stk.size() && h[stk.top()]<=h[j]){
ll v=stk.top();
stk.pop();
ll f;
if(stk.empty()){
f=r[i];
}else{
f=stk.top()-1;
}
res+=(h[j]-h[v])*(f-v+1);
}
stk.push(j);
tmp[j]+=res;
}
while(stk.size())stk.pop();
ll ans=inf;
for(ll j=l[i];j<=r[i];j++){
ans=min(ans,tmp[j]-h[j]);
tmp[j]=0;
}
anS[i]=ans;
}
return anS;
}
vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
if(H.size()<=5000 && L.size()<=5000){
return easy(H,L,R);
}
ll mx=0;
for(auto y:H){
mx=max(mx,(ll)y);
}
if(mx>2 || H.size()>maxn || L.size()>maxn){
exit(1);
}
return solve(H,L,R);
}
