#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "meetings.h"
namespace my {
const int N = 1 << 17;
vector<pair<int, int>> segs;
int f[N], b[N];
int tree[2 * N];
int query(int l, int r) {
int res = 0;
for (l += N, r += N; l <= r; l /= 2, r /= 2) {
if (l % 2 == 1) {
res = max(res, tree[l++]);
}
if (r % 2 == 0) {
res = max(res, tree[r--]);
}
}
return res;
}
}
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
using namespace my;
int n = (int)h.size();
int q = (int)l.size();
vector<ll> c(q);
for (int i = n - 1; i >= 0; --i) {
f[i] = h[i] == 1 ? f[i + 1] + 1 : 0;
}
b[0] = h[0] == 1 ? 1 : 0;
for (int i = 1; i < n; ++i) {
b[i] = h[i] == 1 ? b[i - 1] + 1 : 0;
}
copy_n(f, N, tree + N);
for (int i = N - 1; i > 0; --i) {
tree[i] = max(tree[i + i], tree[i + i + 1]);
}
for (int it = 0; it < q; ++it) {
int lef = l[it], rig = r[it], len = rig - lef + 1;
int mx = min(len, max(f[lef], b[rig]));
lef += f[lef];
rig -= b[rig];
mx = max(mx, query(lef, rig));
c[it] = 2 * len - mx;
}
return c;
}
#ifdef LC
#include "grader.cpp"
#endif
