#include <bits/stdc++.h>
#ifndef SKY
#include "meetings.h"
#endif // SKY
using namespace std;
#define N 200010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back
int n,q,nxt[N],pre[N];
ll a[N];
struct IT
{
int ST[N*4]={};
void update(int id,int l,int r,int i,int val)
{
if(l>i||r<i)
return;
if(l==r)
{
ST[id]=val;
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,i,val);
update(id*2+1,mid+1,r,i,val);
ST[id]=max(ST[id*2],ST[id*2+1]);
}
int get(int id,int l,int r,int u,int v)
{
if(l>v||r<u)
return 0;
if(l>=u&&r<=v)
return ST[id];
int mid=(l+r)/2;
return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
}T;
struct truyvan
{
int l,r,id;
bool operator<(const truyvan&A)const
{
return l<A.l;
}
}tv[N];
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R)
{
n=H.size();
for(int i=0;i<n;i++)
a[i]=H[i],assert(a[i]>=1&&a[i]<=2);
q=L.size();
vector<ll>kq(q);
memset(pre,-1,sizeof(pre));
for(int i=0;i<n+100;i++)
nxt[i]=n;
//memset(nxt,0x3f3f,sizeof(nxt));
for(int i=0;i<n;i++)
if(a[i]==1)
pre[i]=i;
else{
if(i>0)
pre[i]=pre[i-1];
}
for(int i=n-1;i>=0;i--)
if(a[i]==1)
nxt[i]=i;
else nxt[i]=nxt[i+1];
for(int i=0;i<n;i++)
if(a[i]==0&&pre[i]==i-1)
T.update(1,1,n,min(n-1,nxt[i]-1),min(n-1,nxt[i]-1)-i+1);
for(int i=0;i<q;i++)
tv[i]={L[i],R[i],i};
sort(tv,tv+q);
for(int pos=0,t=0;t<=q;t++)
{
int l=tv[t].l,r=tv[t].r;
while(pos<l)
{
if(a[pos]==0&pre[pos]==pos-1)
T.update(1,1,n,min(n-1,nxt[pos]-1),0);
pos++;
}
int res=max(0,T.get(1,1,n,l,r));
if(a[l]==0)
res=max(res,min(r,nxt[l]-1)-max(l,pre[l]+1)+1);
if(a[r]==0)
res=max(res,min(r,nxt[r]-1)-max(l,pre[r]+1)+1);
kq[tv[t].id]=(r-l+1)*2-res;
}
return kq;
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}
#endif
