#include "meetings.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+5;
int n;
struct node{
ll pr, sf, ans, sz;
}t[MAXN*2];
node merge(node &l, node &r){
node res = {0,0,0,l.sz + r.sz};
if(l.pr == l.sz)res.pr = l.sz + r.pr;
else res.pr = l.pr;
if(r.sf == r.sz)res.sf = r.sz + l.sf;
else res.sf = r.sf;
res.ans = max(l.sf + r.pr, max(res.pr, res.sf));
res.ans = max({res.ans, l.ans, r.ans});
return res;
}
int query(int l,int r){
node resl = {0,0,0,0}, resr = {0,0,0,0};
for(l+=n,r+=n; l<=r; l>>=1,r>>=1){
if(l&1)resl = merge(resl, t[l++]);
if(!(r&1))resr=merge(t[r--],resr);
}return merge(resl,resr).ans;
}
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R){
n = h.size();
int Q = L.size();
for(int i=0;i<n;i++){
if(h[i] == 1)t[i+n] = {1,1,1,1};
else t[i+n] = {0,0,0,1};
}for(int i=n-1;i>0;i--)t[i] = merge(t[i<<1],t[i<<1|1]);
vector<ll> ret;
for(int q=0;q<Q;q++){
ll l = L[q], r = R[q];
ll res = query(l,r);
assert(res <= r-l+1);
res += (r-l+1-res)*2ll;
ret.push_back(res);
}return ret;
}
