#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
ll FL[MAXN], FR[MAXN], n;
namespace segment {
int sg[MAXN];
void update(int ind, int val, int l = 0, int r = n - 1, int v = 1) {
if (l == r) sg[v] = val;
else {
int mid = (l + r) >> 1;
if (ind <= mid) update(ind, val, l, mid, v << 1);
else update(ind, val, mid + 1, r, v << 1 | 1);
sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
}
}
int query(int ql, int qr, int l = 0, int r = n - 1, int v = 1) {
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return sg[v];
int mid = (l + r) >> 1;
return max(query(ql, qr, l, mid, v << 1),
query(ql, qr, mid + 1, r, v << 1 | 1));
}
}
vector<ll> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
int Q = L.size();
n = H.size();
vector<ll> ans(Q);
for (int i = 0; i < n; i++) {
FL[i] = (H[i] == 1);
if (i && FL[i]) FL[i] += FL[i - 1];
segment::update(i, FL[i]);
}
for (int i = n - 1; i >= 0; i--) {
FR[i] = (H[i] == 1);
if (FR[i]) FR[i] += FR[i + 1];
}
for (int i = 0; i < Q; i++) {
int l = L[i], r = R[i];
ans[i] = 2 * (r - l + 1);
if (r - FL[r] < l) {
ans[i] = (r - l + 1);
continue;
}
int tans = max(FL[r], FR[l]);
r -= FL[r];
l += FR[l];
tans = max(tans, segment::query(l, r));
ans[i] -= tans;
}
return ans;
}
