#include "meetings.h"
#include <bits/stdc++.h>
#define MAX 1000000000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ii> iii;
int n;
ll val[100010],tma[400010],tl[400010],tr[400010],len[400010];
void init(int node,int a,int b){
if(a==b){
len[node]=1;
tl[node]=tr[node]=tma[node]=(val[a]==1);
return;
}
ll mid=(a+b)/2;
init(2*node+1,a,mid);
init(2*node+2,mid+1,b);
len[node]=(b-a)+1;
if(tma[2*node+1]==len[2*node+1]){
tl[node]=tl[2*node+1]+tl[2*node+2];
}
else tl[node]=tl[2*node+1];
if(tma[2*node+2]==len[2*node+2]){
tr[node]=tr[2*node+2]+tr[2*node+1];
}
else tr[node]=tr[2*node+2];
tma[node]=max(max(tma[2*node+1],tma[2*node+2]),tr[2*node+1]+tl[2*node+2]);
}
iii query(int node,int a,int b,int l,int r){
if(a>r or b<l) return iii(ii(0,0),ii(0,-MAX));
if(l<=a and r>=b){
return iii(ii(tl[node],tr[node]),ii(len[node],tma[node]));
}
int mid=(a+b)/2;
iii le=query(2*node+1,a,mid,l,r),ri=query(2*node+2,mid+1,b,l,r);
/*cout<<node<<endl;
cout<<le.first.first.first<<" "<<le.first.first.second<<" "<<le.first.second.first<<" "<<le.first.second.second<<" "<<le.second<<endl;
cout<<ri.first.first.first<<" "<<ri.first.first.second<<" "<<ri.first.second.first<<" "<<ri.first.second.second<<" "<<ri.second<<endl;*/
ll tm=le.second.first+ri.second.first,l1,r1,ma;
if(le.second.second==le.second.first){
l1=le.second.second+ri.first.first;
}
else l1=le.first.first;
if(ri.second.second==ri.first.second){
r1=ri.second.second+le.first.second;
}
else r1=ri.first.second;
ma=max(max(le.second.second,ri.second.second),le.first.second+ri.first.first);
return iii(ii(l1,r1),ii(tm,ma));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
bool sw=0;
for(int i=0;i<H.size();i++){
if(H[i]>2){
sw=1;
break;
}
else val[i]=H[i];
}
vector<long long> C;
if(sw==1){
for(int i=0;i<L.size();i++){
stack<ii> sl;
vector<ll> le,ri;
ll c=0;
le.push_back(0);
sl.push(ii(H[L[i]],1));
for(int j=L[i]+1;j<=R[i];j++){
ll co=0,t=le.size()-1;
c=le[t]+H[j-1];
while(true){
if(sl.empty() or sl.top().first>H[j]){
sl.push(ii(H[j],co+1));
c+=(H[j]*co);
break;
}
co+=sl.top().second;
c-=(sl.top().first*sl.top().second);
sl.pop();
}
le.push_back(c);
}
while(!sl.empty()) sl.pop();
c=0;
ll t=(R[i]-L[i]);
ri.resize(t+1);
ri[t]=0;
sl.push(ii(H[R[i]],1));
for(int j=R[i]-1;j>=L[i];j--){
ll co=0;
t--;
c=ri[t+1]+H[j+1];
while(true){
if(sl.empty() or sl.top().first>H[j]){
sl.push(ii(H[j],co+1));
c+=(H[j]*co);
break;
}
co+=sl.top().second;
c-=(sl.top().first*sl.top().second);
sl.pop();
}
ri[t]=c;
}
ll res=MAX;
t=0;
for(int j=L[i];j<=R[i];j++){
ll aux=ll(le[t]+ri[t]+H[j]);
res=min(res,aux);
t++;
}
C.push_back(res);
}
}
else{
n=H.size();
init(0,0,n-1);
/* for(int i=0;i<25;i++){
cout<<tl[i]<<" "<<tr[i]<<" "<<len[i]<<" "<<tma[i]<<endl;
}*/
for(int i=0;i<L.size();i++){
iii no=query(0,0,n-1,L[i],R[i]);
ll ret=((R[i]-L[i])+1)-no.second.second;
// cout<<no.second.second<<endl;
ret=no.second.second+(2*ret);
C.push_back(ret);
}
}
return C;
}
