#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SZ(x) int((x).size())
#define lc id << 1
#define rc lc | 1
const ll MAXN = 1e5 + 10;
const ll LOG = 22;
const ll INF = 1e18;
struct Node{
int mx , pref , suff , sz;
};
int n , q , A[MAXN];
Node seg[MAXN << 2];
Node merge(const Node &L , const Node &R){
if(L.sz == 0) return R;
if(R.sz == 0) return L;
Node ans;
ans.mx = max(L.mx , R.mx);
ans.mx = max(ans.mx , L.suff + R.pref);
ans.sz = L.sz + R.sz;
ans.pref = L.pref + (L.pref == L.sz ? R.pref : 0);
ans.suff = R.suff + (R.suff == R.sz ? L.suff : 0);
return ans;
}
void build(int id = 1 , int l = 0 , int r = n){
if(r - l == 1){
seg[id].sz = 1;
if(A[l] == 1){
seg[id].mx = seg[id].pref = seg[id].suff = 1;
}
return;
}
int mid = l + r >> 1;
build(lc , l , mid);
build(rc , mid , r);
seg[id] = merge(seg[lc] , seg[rc]);
}
Node get(int ql , int qr , int id = 1 , int l = 0 , int r = n){
if(qr <= l || r <= ql) return Node();
if(ql <= l && r <= qr) return seg[id];
int mid = l + r >> 1;
return merge(get(ql , qr , lc , l , mid) , get(ql , qr , rc , mid , r));
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = SZ(H); q = SZ(L);
if(n > MAXN){
return {};
}
for(int i = 0 ; i < n ; i++){
A[i] = H[i];
}
build();
vector<ll> ans(q , 0);
for(int i = 0 ; i < q ; i++){
R[i]++;
Node res = get(L[i] , R[i]);
ans[i] = (R[i] - L[i]) * 2 - res.mx;
}
return ans;
}
