#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6;
ll p[N], s[N];
struct node {
int mx, p, s;
bool full;
node (int mx = 0, int p = 0, int s = 0, bool full = 0) : mx(mx), p(p), s(s), full(full) {}
} t[N << 2];
node combine (node a, node b) {
node c;
c.mx = max ({a.mx, b.mx, a.s + b.p});
c.full = a.full && b.full;
c.p = (a.full ? a.p + b.p : a.p);
c.s = (b.full ? b.s + a.s : b.s);
return c;
}
void build (vector<int> &a, int l, int r, int v = 0) {
if (r - l == 1) {
if (a[l] == 1) t[v] = {1, 1, 1, 1};
else t[v] = {0, 0, 0, 0};
return;
}
int m = (l + r) >> 1;
build (a, l, m, v + v + 1);
build (a, m, r, v + v + 2);
t[v] = combine (t[v + v + 1], t[v + v + 2]);
}
node get (int L, int R, int l, int r, int v) {
if (L <= l && r <= R) return t[v];
if (L >= r || l >= R) return {0, 0, 0, 0};
int m = (l + r) >> 1;
return combine (get (L, R, l, m, v +v + 1), get (L, R, m, r, v +v + 2));
}
vector<ll> minimum_costs (vector<int> H, vector<int> L, vector<int> R) {
int Q = L.size();
vector<ll> C(Q);
build(H, 0, H.size());
for (int query = 0 ; query < Q ; ++ query) {
int l = L[query], r = R[query];
C[query] = 2 * (r - l + 1) - get (l, r + 1, 0, H.size(), 0).mx;
}
return C;
}
