#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define inf (ll)1e17
#define dbg(x) cerr<< #x << ' ' << x << endl;
using namespace std;
ll maxn=1e5;
vector<vector<ll>> tree(4*maxn+3,vector<ll>(3));
vector<vector<ll>> lr;
void merge(ll node, ll l, ll r)
{
tree[node][0]=max({tree[node*2+1][0],tree[node*2+2][0],tree[node*2+1][2]+tree[node*2+2][1]});
if(lr[l][1]!=-1)
{
tree[node][1]=(lr[l][1]-l)+1;
}
if(lr[r][0]!=-1)
{
tree[node][0]=r-lr[r][0]+1;
}
tree[node][1]=min(tree[node][1],r-l+1);
tree[node][0]=min(tree[node][0],r-l+1);
}
void update(ll node, ll l, ll r, ll pos)
{
if(pos < l || pos > r)return;
if(l==r)
{
tree[node]={1,1,1};
return;
}
ll mid=(l+r)>>1;
update(node*2+1,l,mid,pos);
update(node*2+2,mid+1,r,pos);
merge(node,l,r);
}
ll query(ll node, ll l, ll r, ll x, ll y)
{
if(max(l,x) > min(r,y)) return 0;
if(x<=l && r<=y)
{
return tree[node][0];
}
ll mid=(l+r)>>1;
ll qr1=query(node*2+1,l,mid,x,y);
ll qr2=query(node*2+2,mid+1,r,x,y);
ll val1=0;
ll val2=0;
if(lr[mid][0]!=-1)
{
val1=min(mid-l+1,mid-lr[mid][0]+1);
}
if(lr[mid+1][1]!=-1)
{
val2=min(r-mid,lr[mid+1][1]-mid);
}
return max({val1+val2,qr1,qr2});
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R)
{
ll n=H.size();
ll q=L.size();
ll l=-1;
ll r=-1;
lr.assign(n,vector<ll>(2,-1));
for (int i=0;i<n;i++)
{
if(H[i]==1 && (i==0 || H[i-1]==2))
{
l=i;
}
if(H[i]==1 && (i==n-1 || H[i+1]==2))
{
r=i;
}
if(l==-1 || r==-1)continue;
for (int j=l;j<=r;j++)
{
lr[j][0]=l;
lr[j][1]=r;
}
l=-1;
r=-1;
}
for (int i=0;i<n;i++)
{
if(H[i]==1)
{
update(0,0,n-1,i);
}
}
vector<ll> ans(q);
for (int i=0;i<q;i++)
{
ans[i]=2*(R[i]-L[i]+1)-query(0,0,n-1,L[i],R[i]);
}
return ans;
}
