#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Segment{
int l,r,m;
bool full;
Segment(){
l=r=m=0;
full=false;
}
Segment(int a,int b,int c,bool d){
l=a;r=b;m=c;
full=d;
}
};
vector<int> h={0};
vector<Segment> seg;
void build(int id,int l,int r){
// cout << id << ' ' << l << ' ' << r << endl;
if(l==r){
if(h[l]==1){
seg[id]=Segment(1,1,1,true);
}else{
seg[id]=Segment(0,0,0,false);
}
return;
}
int m=l+(r-l)/2;
build(id*2,l,m);
build(id*2+1,m+1,r);
seg[id]=Segment();
if(seg[id*2].full){
seg[id].l=seg[id*2].l+seg[id*2+1].l;
}else{
seg[id].l=seg[id*2].l;
}
if(seg[id*2+1].full){
seg[id].r=seg[id*2+1].r+seg[id*2].r;
}else{
seg[id].r=seg[id*2+1].r;
}
seg[id].m=max(seg[id*2].r+seg[id*2+1].l,max(seg[id*2].m,seg[id*2+1].m));
seg[id].full=seg[id*2].full&&seg[id*2+1].full;
}
Segment query(int id,int l,int r,int L,int R){
if(r<L||l>R){
return Segment(0,0,0,false);
}else if(l>=L&&r<=R){
return seg[id];
}
int m=l+(r-l)/2;
Segment a=query(id*2,l,m,L,R),b=query(id*2+1,m+1,r,L,R),ans;
if(a.full){
ans.l=a.l+b.l;
}else{
ans.l=a.l;
}
if(b.full){
ans.r=a.r+b.r;
}else{
ans.r=b.r;
}
ans.m=max(a.r+b.l,max(a.m,b.m));
ans.full=a.full&&b.full;
return ans;
}
std::vector<long long> minimum_costs(std::vector<int32_t> H, std::vector<int32_t> L,
std::vector<int32_t> R) {
int N=H.size(),Q = L.size(),cnt;
Segment tmp;
vector<long long> C(Q);
for(int i=0;i<N;i++){
h.push_back(H[i]);
}
seg.resize(4*N);
build(1,1,N);
for(int i=0;i<Q;i++){
tmp=query(1,1,N,L[i]+1,R[i]+1);
cnt=max(tmp.m,max(tmp.l,tmp.r));
C[i]=(R[i]-L[i]+1)*2-cnt;
}
return C;
}
