#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
int suffix;
int prefix;
int best;
int l, r;
Node(int _s, int _p, int _b, int _l, int _r) {
suffix = _s;
prefix = _p;
best = _b;
l = _l;
r = _r;
}
};
const Node ID = Node(0,0,0,-1, -1);
vector<Node> ST;
vector<int> h;
int N,n;
int L(int i) {return 2*i;}
int R(int i) {return 2*i + 1;}
Node merge(Node v1, Node v2) {
if(v1.l == -1) return Node(v2);
if(v2.l == -1) return Node(v1);
int nb = max(v1.suffix + v2.prefix, max(v1.best, v2.best));
int np = (v1.prefix == v1.r - v1.l + 1) ? (v1.prefix + v2.prefix) : (v1.prefix);
int ns = (v2.suffix == v2.r - v2.l + 1) ? (v2.suffix + v1.suffix) : (v2.suffix);
int nl = v1.l;
int nr = v2.r;
return Node(ns, np, nb, nl, nr);
}
void build(int i, int l, int r) {
if(l == r) {
if(h[l] == 1) {
ST[i] = Node(1, 1, 1, l, r);
} else {
ST[i] = Node(0, 0, 0, l, r);
}
return;
}
int m = (l+r)/2;
build(L(i), l, m);
build(R(i), m+1, r);
ST[i] = merge(ST[L(i)], ST[R(i)]);
}
Node query(int i, int l, int r, int a, int b) {
if(l > r || a > r || b < l) return ID;
if(a <= l && r <= b) return ST[i];
int m = (l+r)/2;
return merge(query(L(i), l, m, a, b), query(R(i), m+1, r, a, b));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
h = H;
N = n = H.size();
int Q;
Q = L.size();
ST.resize(4*n, ID);
build(1, 0, n-1);
vector<ll> ans(Q, -1);
for(int i = 0; i < Q; i++) {
Node p = query(1, 0, n-1, L[i], R[i]);
ll pb = p.best;
ll r = R[i];
ll l = L[i];
ans[i] = 2*(r-l+1) - pb;
}
return ans;
}
