#include "meetings.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=100090;
ll n;int h[N],y[N],go[N],tree[N*4];
void build(int ind,int st,int end)
{
if(st==end)
{
tree[ind]=y[st];return ;
}
int m=(st+end)/2;
build(ind*2+1,st,m);
build(ind*2+2,m+1,end);
tree[ind]=max(tree[ind*2+1],tree[ind*2+2]);
}
int get (int ind,int st,int end,int l,int r)
{
if(l>end||r<st)return 0;
if(l<=st&&end<=r)return tree[ind];
int m=(st+end)/2;
return max(get(ind*2+1,st,m,l,r),get(ind*2+2,m+1,end,l,r));
}
int solve (int l,int r)
{
int z=r-l+1;z*=2;int x=0;//cout<<l<<" "<<r<<endl;
if(h[r]==2)
{
x=get(0,0,n-1,l,r);
z-=x;
return z;
}
int rr=r-go[r];
//cout<<l<<" "<<go[r]<<" "<<r<<endl;
if(rr<l)return (r-l+1);
x=max(x,r-rr);
x=max(x,get(0,0,n-1,l,rr));
z-=x;
return z;
}
vector<ll>ans;
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
ans.clear();
n=H.size();
for(int i=0;i<n;i++)
h[i]=H[i];
for(int i=n-1;i>-1;i--)
{
if(h[i]==2)continue;
y[i]=y[i+1]+1;
}
for(int i=0;i<n;i++)
{
if(h[i]==2)continue;
go[i]=go[i-1]+1;
}
/*
for(int i=0;i<n;i++)
{
cout<<go[i]<<" "<<y[i]<<endl;
}
return ans;*/
build(0,0,n-1);
int q=L.size();
for(int i=0;i<q;i++)
{
//cout<<L[i]<<" "<<R[i]<<endl;
ans.pb(solve(L[i],R[i]));
}
return ans;
}
/*
5 5
1 2 1 1 1
0 2
1 3
0 4
1 1
3 3
*/
