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