#include "bits/stdc++.h"
#include "meetings.h"
using namespace std;
struct node
{
int pref, suff, mx, sz;
};
node merge(node a, node b)
{
node c;
c.pref = a.pref;
c.suff = b.suff;
if (a.pref == a.sz)
c.pref = a.sz + b.pref;
if (b.suff == b.sz)
c.suff = a.suff + b.sz;
c.sz = a.sz + b.sz;
c.mx = max({a.mx, b.mx, a.suff + b.pref});
return c;
}
vector<node> t(4e5);
void upd(int pos, int l, int r, int i)
{
if (l == r)
t[i].pref = t[i].suff = t[i].mx = 1;
else
{
int m = (l + r) / 2;
if (pos <= m)
upd(pos, l, m, i * 2);
else
upd(pos, m + 1, r, i * 2 + 1);
t[i] = merge(t[i * 2], t[i * 2 + 1]);
}
}
node get(int l, int r, int tl, int tr, int i = 1)
{
if (l > tr || tl > r)
return t[0];
if (l <= tl && tr <= r)
return t[i];
int m = (tl + tr) / 2;
return merge(get(l, r, tl, m, i * 2), get(l, r, m + 1, tr, i * 2 + 1));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
for (auto &i : t)
i.sz = 1;
int q = L.size();
int n = H.size();
vector<long long> ans(q, 1e18);
for (int i = 0; i < n; i++)
if (H[i] == 1)
upd(i, 0, n - 1, 1);
for (int i = 0; i < q; i++)
ans[i] = 2 * (R[i] - L[i] + 1) - get(L[i], R[i], 0, n - 1).mx;
return ans;
}
