#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const ll N=1e5;
#define MID ((l+r)/2)
ll b[N]={};
struct node{
ll val;
node *L, *R;
void init(ll l, ll r){
if(l==r) val=b[l];
else{
L=new node;
L->init(l,MID);
R=new node;
R->init(MID+1,r);
val=max(L->val,R->val);
}
}
ll ans(ll l, ll r, ll tl, ll tr){
if(tl<=l && r<=tr) return val;
else if(r<tl || tr<l) return 0;
else return max(L->ans(l,MID,tl,tr),R->ans(MID+1,r,tl,tr));
}
};
vector<ll> minimum_costs(vector<int> a, vector<int> l, vector<int> r){
ll n=a.size(), q=l.size();
ll nxt[n], prev[n];
ll curr=-1;
for(ll i=0; i<n; i++){
if(a[i]==2) curr=i;
prev[i]=curr;
}
curr=n;
for(ll i=n-1; i>=0; i--){
if(a[i]==2) curr=i;
nxt[i]=curr;
}
if(a[0]==1) b[0]=1;
for(ll i=1; i<n; i++){
if(a[i]==1) b[i]=b[i-1]+1;
}
node seg;
seg.init(0,n-1);
vector<ll> ans;
for(ll i=0; i<q; i++){
ans.push_back(2*(r[i]-l[i]+1)-max({seg.ans(0,n-1,nxt[l[i]],prev[r[i]]),nxt[l[i]]-l[i],r[i]-prev[r[i]]}));
}
return ans;
}
