#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Seg {
struct Node {
int l, r, tot;
static Node join(Node const& a, Node const& b) {
return Node{a.l,
b.r,
max({a.tot, b.tot, a.r+b.l})};
}
};
vector<Node> tree;
vector<int> const& v;
Seg(vector<int> const& v) : tree(v.size()*4), v(v) {
build(0, 0, v.size());
}
void build(int no, int l, int r) {
if (l == r) {
if (v[l] == 1) tree[no] = Node{1, 1, 1};
else tree[no] = Node{0, 0, 0};
}
else {
int m = (l+r)/2;
build(no*2+1, l, m);
build(no*2+2, m+1, r);
tree[no] = Node::join(tree[no*2+1], tree[no*2+2]);
}
}
Node get(int no, int l, int r, int a, int b) {
if (a <= l and r <= b) return tree[no];
else {
int m = (l+r)/2;
if (b <= m) return get(no*2+1, l, m, a, b);
if (a > m) return get(no*2+2, m+1, r, a, b);
return Node::join(get(no*2+1, l, m, a, b),
get(no*2+2, m+1, r, a, b));
}
}
};
vector<ll> minimum_costs(vector<int> h, vector<int> L,
vector<int> R) {
int n = h.size();
Seg sg(h);
int q = L.size();
vector<ll> res;
for (int at = 0; at < q; at++) {
int l = L[at], r = R[at];
Seg::Node ans = sg.get(0, 0, n-1, l, r);
res.push_back(2ll*(r-l+1) - ans.tot);
}
return res;
}
