#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define ll long long
#define ALL(x) x.begin(), x.end()
// solving subtask 1 + 2 in O(N^2 + QN) time
const ll LLINF = 1ll<<60;
const int maxn = 1e5 + 10;
int n, q, tree[maxn * 4] = {0};
vector<int> two;
void update(int x, int v, int tl = 0, int tr = maxn, int i = 1){
if (tl > x || tr < x) return;
if (tl == tr){
tree[i] = v; return;
}
int tm = (tl + tr) / 2;
update(x, v, tl, tm, i * 2); update(x, v, tm + 1, tr, i * 2 + 1);
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
int query(int l, int r, int tl = 0, int tr = maxn, int i = 1){
if (l > tr || tl > r) return 0;
if (l <= tl && tr <= r) return tree[i];
int tm = (tl + tr) / 2;
return max(query(l, r, tl, tm, i * 2),
query(l, r, tm + 1, tr, i * 2 + 1));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
n = H.size();
int last = -1;
for (int i = 1; i < n; i++){
if (H[i] == 2){
update(last + 1, i - last - 1);
last = i; two.push_back(last + 1);
}
}
update(last + 1, n - last - 1);
two.push_back(last + 1);
q = L.size();
vector<ll> c(q);
for (int i = 0; i < q; i++){
int l = lower_bound(ALL(two), L[i]) - two.begin();
int r = upper_bound(ALL(two), R[i]) - two.begin() - 1;
l = two[l], r = two[r];
int mx = max({query(l, r), (l - 1) - L[i], R[i] - (r - 1)});
// cout << mx << ' ' << query(l, r) << endl;
c[i] = (R[i] - L[i] + 1) * 2 - mx;
}
return c;
}
