using namespace std;
#include <vector>
#define ll long long
#define vll vector<ll>
#include <bits/stdc++.h>
vll h;
struct node{
int l,r,mid,ones,pref,suf;
node* sl,*sr;
node(int li, int ri){
l = li, r = ri, mid = (l+r)/2;
if(l<r){
sl = new node(l,mid);
sr = new node(mid+1,r);
if(sl->ones == mid-l+1)pref = r-l+1 + sr->pref;
else pref = sl->pref;
if(sr->ones == r-mid)suf = r-mid+sl->suf;
else suf = sr->suf;
ones = max({sl->ones,sr->ones,sl->suf+sr->pref});
}else{
ones = h[l]%2;
pref=ones, suf = pref;
}
}
int query(int a, int b){
if(a > r || b < l)return 0;
if(a <= l && b>=r)return ones;
if(a > mid)return sr->query(a,b);
if(b <= mid)return sl->query(a,b);
return max({sl->query(a,b),sr->query(a,b),min(sl->suf,mid-a+1)+min(sr->pref,b-mid)});
}
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
for(int hi :H)h.push_back(hi);
int Q = L.size();
std::vector<ll> ans(Q);
int N= H.size();
node* seg = new node(0,N-1);
for (int j = 0; j < Q; ++j) {
ans[j] = 2*(R[j]-L[j]+1) -seg->query(L[j],R[j]);
}
return ans;
}
