#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R){
int n=H.size(),q=L.size();
set<int> two,two2;
two.insert(-1);two.insert(n);
two2.insert(1);two2.insert(-n);
for(int i=0;i<n;i++){
if(H[i]==2){
two.insert(i);
two2.insert(-i);
}
}
vector<long long> ans(q);
vector<int> v(n);
vector<vector<int>> maxr(n,vector<int>(18));
for(int i=0;i<n;i++){
v[i]=*(two.lower_bound(i))+*(two2.lower_bound(-i))-1;
v[i]=max(v[i],0);
maxr[i][0]=v[i];
}
for(int t=1;t<18;t++){
for(int i=0;i<n-(1<<(t-1));i++){
maxr[i][t]=max(maxr[i][t-1],maxr[i+(1<<(t-1))][t-1]);
}
}
for(int t=0;t<q;t++){
int lf=*(two.lower_bound(L[t])),rg=0-(*(two2.lower_bound(-R[t]))),bst;
//cout<<(*two2.lower_bound(R[t]));
if(lf>R[t]){
ans[t]=R[t]-L[t]+1;
continue;
}
else ans[t]=R[t]-L[t]+1+min(R[t]-lf+1,rg-L[t]+1);
bst=log2(rg-lf+1);
bst=max(maxr[lf][bst],maxr[rg-(1<<bst)+1][bst]);
ans[t]=min(int(ans[t]),2*(R[t]-L[t]+1)-bst);
}
return ans;
}
