#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Inf = 1e18;
struct Segtree {
vector<ll> ma;
int n;
Segtree (int _n) : n(_n), ma(4 * _n) {}
void update (int i, int sl, int sr, int pos, ll x) {
if (sr - sl == 1) {
ma[i] = x;
return;
}
int mid = sl + sr >> 1;
if (pos < mid) update(2 * i, sl, mid, pos, x);
else update(2 * i + 1, mid, sr, pos, x);
ma[i] = max(ma[2 * i], ma[2 * i + 1]);
}
void update (int i, ll x) {
update(1, 0, n, i, x);
}
ll get (int i, int sl, int sr, int l, int r) {
if (sl >= r || sr <= l) return 0;
if (sl >= l && sr <= r) return ma[i];
int mid = sl + sr >> 1;
return max(get(2 * i, sl, mid, l, r), get(2 * i + 1, mid, sr, l, r));
}
ll get (int l, int r) {
return get(1, 0, n, l, r);
}
};
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
int q = l.size();
int n = h.size();
vector<ll> ans(q, Inf);
Segtree st(n);
vector<ll> ps(n), left(n, -1), right(n, n);
for (int i = 0; i < n; i++) {
if (i) {
ps[i] = ps[i - 1];
left[i] = left[i - 1];
}
if (h[i] == 1) {
ps[i]++;
} else {
left[i] = i;
ps[i] = 0;
}
st.update(i, ps[i]);
}
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1) right[i] = right[i + 1];
if (h[i] == 2) {
right[i] = i;
}
}
for (int i = 0; i < q; i++) {
ll len = r[i] - l[i] + 1;
ll ma = 0;
if (h[l[i]] == 1) {
ma = max(ma, right[l[i]] - l[i]);
}
if (h[r[i]] == 1) {
ma = max(ma, r[i] - left[r[i]]);
}
ma = min(ma, len);
r[i] = left[r[i]];
l[i] = right[l[i]];
if (l[i] <= r[i]) {
ma = max(ma, st.get(l[i], r[i] + 1));
}
ans[i] = 2 * len - ma;
}
return ans;
}
