#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
struct SegTree {
struct Node {
ll ans;
ll pref, suff;
bool isWhole;
Node operator+ (const Node &o) const {
return {
max({ ans, o.ans, suff + o.pref }),
isWhole ? ans + o.pref : pref,
o.isWhole ? suff + o.ans : o.suff,
isWhole && o.isWhole
};
}
};
vector <Node> tree;
ll n;
SegTree (ll n): tree(2*n, Node{ 0, 0, 0, true }), n(n) {}
void update (ll id, ll val) {
for (tree[id += n] = Node{ val, val, val, !!val }; id > 1; id >>= 1)
tree[id>>1] = tree[id&~1] + tree[id|1];
}
Node query (ll ql, ll qr) {
Node ansL = Node{ 0, 0, 0, true }, ansR = Node{ 0, 0, 0, true };
for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
if (ql&1) ansL = ansL + tree[ql++];
if (qr&1) ansR = tree[--qr] + ansR;
}
return ansL + ansR;
}
};
vll minimum_costs (vi H, vi l, vi r) {
vll ve(H.begin(), H.end());
ll n = ve.size();
SegTree st(n);
for (ll i = 0; i < n; i++) st.update(i, 2-ve[i]);
ll Q = l.size();
vll ans(Q, -15);
for (ll q = 0; q < Q; q++) {
ans[q] = 2*(r[q]-l[q]+1)-st.query(l[q], r[q]).ans;
}
return ans;
}
