#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
using pii=pair<int,int>;
vector<int>minimum_costs(vector<signed>h,vector<signed>l,vector<signed>r){
int n=h.size();
int q=l.size();
for(int i=0;i<n;i++){
assert(h[i]<=2);
h[i]-=1;
}
int last[n]{};
int suf[n]{};
for(int i=n-1;0<=i;i--){
last[i]=i;
if(i+1<n&&!h[i+1])last[i]=last[i+1];
if(!h[i]){
suf[i]=1;
if(i+1<n)suf[i]+=suf[i+1];
}
}
int pref[n]{};
for(int i=0;i<n;i++){
if(!h[i]){
pref[i]=1;
if(i){
pref[i]+=pref[i-1];
}
}
}
vector<int>c(q,0);
vector<int>inds[n];
for(int i=0;i<q;i++){
inds[l[i]].pb(i);
}
deque<pii>ranges;
for(int i=n-1;0<=i;i--){
if(pref[i]==1){
pii toad={i+suf[i]-1,suf[i]};
while(ranges.size()&&ranges[0].second<suf[i])ranges.pop_front();
ranges.push_front(toad);
}
for(int id:inds[i]){
auto p=upper_bound(ranges.begin(),ranges.end(),pii{r[id],INT_MAX});
if(p!=ranges.begin()){
p--;
c[id]=p->second;
}
if(!h[r[id]]){
c[id]=max(c[id],pref[r[id]]);
}
if(!h[i]){
c[id]=max(c[id],suf[i]);
}
c[id]=min<int>(c[id],r[id]-i+1);
c[id]=2*(r[id]-i+1)-c[id];
}
}
return c;
}
// std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
// std::vector<int> R) {
// int Q = L.size();
// std::vector<long long> C(Q);
// for (int j = 0; j < Q; ++j) {
// C[j] = H[L[j]];
// }
// return C;
// }
#undef int
