#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;
typedef pair<iii,ll> iiii;
int n;
int val[100010],tma[400010],tl[400010],tr[400010],l1[400010],r1[400010];
void init(int node,int a,int b){
if(a==b){
l1[node]=r1[node]=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);
tma[node]=max(tma[2*node+1],tma[2*node+2]);
if(tr[2*node+1]==1 and tl[2*node+2]==1){
tma[node]=max(tma[node],r1[2*node+1]+l1[2*node+2]);
}
if(tl[2*node+1]==1 and tr[2*node+1]==1 and tma[2*node+1]==abs(a-mid)+1){
l1[node]=l1[2*node+1]+l1[2*node+2];
}
else l1[node]=l1[2*node+1];
if(tr[2*node+2]==1 and tl[2*node+2]==1 and tma[2*node+2]==abs((mid+1)-b)+1){
r1[node]=r1[2*node+1]+r1[2*node+2];
}
else r1[node]=r1[2*node+2];
tl[node]=tl[2*node+1];
tr[node]=tr[2*node+2];
}
iiii query(int node,int a,int b,int l,int r){
// cout<<node<<endl;
if(a>r or b<l) return iiii(iii(ii(0,0),ii(0,0)),-MAX);
if(l<=a and r>=b){
return iiii(iii(ii(tl[node],l1[node]),ii(tr[node],r1[node])),tma[node]);
}
int mid=(a+b)/2;
iiii 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 ma=-1;
ll al,ar,a1,b1;
ma=max(le.second,ri.second);
if(le.first.second.first==1 and ri.first.first.first==1){
ma=max(ma,le.first.second.second+ri.first.first.second);
}
if(le.first.first.first==1 and le.first.second.first==1 and le.second==(mid-a)+1){
a1=le.first.first.second+ri.first.first.second;
}
else a1=le.first.first.second;
if(ri.first.first.first==1 and ri.first.second.first==1 and ri.second==(b-(mid+1))+1){
b1=le.first.second.second+ri.first.second.second;
}
else b1=le.first.second.second;
al=le.first.first.first;
ar=ri.first.second.first;
return iiii(iii(ii(al,a1),ii(ar,b1)),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<17;i++){
cout<<i<<": "<<tl[i]<<" "<<l1[i]<<" "<<tr[i]<<" "<<r1[i]<<" "<<tma[i]<<endl;
}*/
for(int i=0;i<L.size();i++){
iiii no=query(0,0,n-1,L[i],R[i]);
ll ret=((R[i]-L[i])+1)-no.second;
// cout<<no.second<<endl;
C.push_back(no.second+(2*ret));
}
}
return C;
}
