#include "meetings.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
typedef vector <ll> vecl;
using namespace std;
const int INF = 9;
int n,Q;
vecl ans;
int a[7500005];
struct Tree {int l,r,mx,s;}t[4000005];
Tree f(Tree l,Tree r) {
Tree ret;
ret.s = l.s&r.s;
ret.l = (l.s ? l.mx+r.l : l.l);
ret.r = (r.s ? r.mx+l.r : r.r);
ret.mx = max({l.mx,r.mx,l.r+r.l});
return ret;
}
void build(int x,int l,int r) {
if(l == r) {
if(a[l] == 1) t[x] = {1,1,1,1};
else t[x] = {0,0,0,0};
return;
}
int mid = (l + r) >> 1;
build(x*2,l,mid), build(x*2+1,mid+1,r);
t[x] = f(t[x*2],t[x*2+1]);
}
Tree query(int x,int l,int r,int rl,int rr) {
if(rl > r||l > rr) return {0,0,0,0};
if(rl <= l&&r <= rr) return t[x];
int mid = (l + r) >> 1;
return f(query(x*2,l,mid,rl,rr),query(x*2+1,mid+1,r,rl,rr));
}
void debug(int x,int l,int r) {
//cout << l << " ~ " << r << " : " << t[x].x << ' ' << t[x].cnt << '\n';
if(l == r) {
return;
}
int mid = (l + r) >> 1;
debug(x*2,l,mid), debug(x*2+1,mid+1,r);
t[x] = f(t[x*2],t[x*2+1]);
}
vecl minimum_costs(vec H,vec L,vec R) {
n = H.size(), Q = L.size();
for(int i = 0;i < n;i++) a[i+1] = H[i];
ans.resize(Q);
build(1,1,n);
for(int t = 0;t < Q;t++) {
int l = L[t]+1, r = R[t]+1;
Tree val = query(1,1,n,l,r);
ans[t] = 2*(r-l+1)-val.mx;
}
return ans;
}
