#include "meetings.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define pob pop_back()
#define iter(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
using pll = pair<ll, ll>;
struct Node{
int v = 0, l = 0, r = 0, sz = 0;
};
vector<int> h;
vector<Node> st;
Node mergenode(Node ln, Node rn){
int v = max({ln.v, rn.v, ln.r + rn.l});
int l = ln.v == ln.sz ? ln.v + rn.l : ln.l;
int r = rn.v == rn.sz ? rn.v + ln.r : rn.r;
int sz = rn.sz + ln.sz;
return Node({v, l, r, sz});
}
void build(int l, int r, int id){
if(l == r){
st[id].sz = r - l + 1;
st[id].v = st[id].l = st[id].r = (h[l] == 1);
return;
}
int m = (l + r) / 2;
build(l, m, 2 * id + 1);
build(m + 1, r, 2 * id + 2);
st[id] = mergenode(st[2 * id + 1], st[2 * id + 2]);
}
Node query(int l, int r, int L, int R, int id){
if(l == L && r == R){
return st[id];
}
int M = (L + R) / 2;
if(r <= M) return query(l, r, L, M, 2 * id + 1);
else if(l > M) return query(l, r, M + 1, R, 2 * id + 2);
else{
return mergenode(query(l, M, L, M, 2 * id + 1), query(M + 1, r, M + 1, R, 2 * id + 2));
}
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
h = H;
int m = L.size();
int n = h.size();
st.resize(4 * n);
build(0, n - 1, 0);
vector<ll> c(m);
for(int i = 0; i < m; i++){
int tmp = query(L[i], R[i], 0, n - 1, 0).v;
//cerr << tmp << "\n";
c[i] = tmp + (R[i] - L[i] + 1 - tmp) * 2;
}
return c;
}
