#include"meetings.h"
#include<bits/stdc++.h>
#ifndef EVAL
#include"grader.cpp"
#endif
using namespace std;
typedef long long ll;
ll n,q;
struct node{
int pref,suf,sum,ans;
bool well;
}tree[400005];
node mk(bool val){
node res;
res.pref=res.suf=res.sum=res.well=res.ans=val;
return res;
}
node combine(node l,node r){
node res;
res.well=(l.well&r.well);
res.sum=l.sum+r.sum;
res.pref=l.pref;
if(l.well)res.pref=max(res.pref,l.sum+r.pref);
res.suf=r.suf;
if(r.well)res.suf=max(res.suf,r.sum+l.suf);
res.ans=max(max(l.suf+r.pref,max(l.pref,r.suf)),max(l.ans,r.ans));
return res;
}
void update(int v,int l,int r,int pos,bool val){
if(l==r){
tree[v]=mk(val);
return;
}
int mid=(l+r)>>1;
if(pos<=mid)update(v<<1,l,mid,pos,val);
else update(v<<1|1,mid+1,r,pos,val);
tree[v]=combine(tree[v<<1],tree[v<<1|1]);
}
node get(int v,int l,int r,int ql,int qr){
if(qr<l||r<ql)return mk(0);
if(ql<=l&&r<=qr)return tree[v];
int mid=(l+r)>>1;
return combine(get(v<<1,l,mid,ql,qr),get(v<<1|1,mid+1,r,ql,qr));
}
vector<ll>minimum_costs(vector<int>h,vector<int>l,vector<int>r){
n=h.size();
q=l.size();
for(int i=0;i<n;i++)
update(1,0,n-1,i,2-h[i]);
vector<ll>rs;
for(int i=0;i<q;i++){
ll ans=(r[i]-l[i]+1)<<1ll;
ans-=get(1,0,n-1,l[i],r[i]).ans;
rs.push_back(ans);
}
return rs;
}
