#include "meetings.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 5e3+1, inf = 2e9;
vi h;
struct Node {
int ans,pref,suf,sz;
};
Node merge(Node a,Node b) {
Node ret;
ret.ans = max({a.ans,b.ans,a.suf+b.pref});
ret.pref = (a.pref == a.sz)?(a.pref+b.pref):a.pref;
ret.suf = (b.suf == b.sz)?(a.suf+b.suf):b.suf;
ret.sz = a.sz+b.sz;
return ret;
}
struct ST {
vector<Node> t;
void build(int node,int l,int r) {
if (l == r) {
t[node] ={0,0,0,1};
return;
}
int m = (l+r) >> 1;
build(2*node,l,m),build(2*node+1,m+1,r);
t[node] = merge(t[2*node],t[2*node+1]);
}
ST(int nn) {
t.resize(4*nn+1);
build(1,1,nn);
}
void update(int node,int l,int r,int p,int v) {
if (!v) return;
if (l == r) {
t[node] = {1,1,1,1};
return;
}
int m = (l+r) >> 1;
if (p <= m) update(2*node,l,m,p,v);
else update(2*node+1,m+1,r,p,v);
t[node] = merge(t[2*node],t[2*node+1]);
}
Node query(int node,int l,int r,int L,int R) {
if (l > R || r < L) return {0,0,0,1};
if (l >= L && r <= R) return t[node];
int m = (l+r) >> 1;
return merge(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
}
};
vi minimum_costs(std::vector<signed> H, std::vector<signed> L,
std::vector<signed> R) {
ST st(big(H));
h = vi(all(H));
for (int i = 0;i<big(H);i++) st.update(1,1,big(H),i+1,h[i] == 1);
vi answer(big(L));
for (int i = 0;i<big(L);i++) {
answer[i] = 2*(R[i]-L[i]+1)-st.query(1,1,big(H),L[i]+1,R[i]+1).ans;
}
return answer;
}
