#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int N;
vector<vector<ll>> st;
vector<ll> merge(vector<ll> l, vector<ll> r){
vector<ll> res(4, 0);
res[3] = l[3]+r[3];
res[0] = max(max(l[0], r[0]), l[2]+r[1]);
if (l[1] == l[3]) res[1] = l[1]+r[1];
else res[1] = l[1];
if (r[2] == r[3]) res[2] = l[2]+r[2];
else res[2] = r[2];
return res;
}
void update(int pos, int val, int node=1, int tl=0, int tr=N-1){
if (tl == tr){
st[node] = {val, val, val, 1};
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) update(pos, val, node*2, tl, tm);
else update(pos, val, node*2+1, tm+1, tr);
st[node] = merge(st[node*2], st[node*2+1]);
}
vector<ll> query(int l, int r, int node=1, int tl=0, int tr=N-1){
if (tr < l || r < tl) return {0, 0, 0, 0};
if (l <= tl && tr <= r) return st[node];
int tm = (tl+tr)/2;
return merge(query(l, r, node*2, tl, tm), query(l, r, node*2+1, tm+1, tr));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
N = H.size();
int Q = L.size();
st.resize(4*N, vector<ll>(4, 0));
for (int i=0; i<N; i++){
if (H[i] == 1) update(i, 1);
else update(i, 0);
}
vector<ll> C(Q);
for (int i=0; i<Q; i++) C[i] = 2*(R[i]-L[i]+1)-query(L[i], R[i])[0];
return C;
}
