#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "meetings.h"
const long long inf = 1e17;
struct SEGT{
struct node{
int pre, suf, ans, sz;
node(){
pre = suf = ans = sz = 0;
}
};
node merge(node a, node b){
node res = node();
res.sz = a.sz + b.sz;
res.pre = a.pre + (a.pre == a.sz ? b.pre : 0);
res.suf = b.suf + (b.suf == b.sz ? a.suf : 0);
res.ans = max({a.ans, b.ans, a.suf + b.pre});
return res;
}
vector<node> tree;
void init(int n){
tree.assign(4*n, node());
}
void build(int ind, int l, int r, vector<int> &a){
if(l == r){
tree[ind].sz = 1;
if(a[l-1] == 1){
tree[ind].pre = tree[ind].suf = tree[ind].ans = 1;
}
}
else{
int m = (l + r)/2;
build(ind*2, l, m, a);
build(ind*2+1, m+1, r, a);
tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
}
}
node _query(int ind, int l, int r, int ql, int qr){
if(l > r || l > qr || r < ql) return node();
if(l >= ql && r <= qr) return tree[ind];
else{
int m = (l + r)/2;
return merge(_query(ind*2, l, m, ql, qr), _query(ind*2+1, m+1, r, ql, qr));
}
}
int query(int l, int r){
return _query(1, 1, tree.size()/4, l, r).ans;
}
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int n = H.size();
SEGT seg;
seg.init(n);
seg.build(1, 1, n, H);
int Q = L.size();
vector<long long> C(Q);
for (int j = 0; j < Q; ++j) {
int ans = 2 * (R[j] - L[j] + 1) - seg.query(L[j] + 1, R[j] + 1);
C[j] = ans;
}
return C;
}
