//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "meetings.h"
const int maxn = 1e5+10;
pair<int,pii> tree[maxn*4];
int h[maxn];
int n;
pair<int,pii> merge(pair<int,pii> a,pair<int,pii> b,int lsz,int rsz) {
pair<int,pii> ret;
ret.se.fi = a.se.fi;
if (a.se.fi==lsz) ret.se.fi += b.se.fi;
ret.se.se = b.se.se;
if (b.se.se==rsz) ret.se.se += a.se.se;
ret.fi = max(a.fi,b.fi);
ret.fi = max(ret.fi,a.se.se+b.se.fi);
return ret;
}
void init(int c,int cl,int cr) {
if (cl==cr) {
int tmp = (h[cl]==1);
tree[c] = {tmp,{tmp,tmp}};
return;
}
int mid=cl+cr>>1;
init(c<<1,cl,mid);
init(c<<1|1,mid+1,cr);
tree[c] = merge(tree[c<<1],tree[c<<1|1],mid-cl+1,cr-mid);
}
pair <int,pii> query(int c,int cl,int cr,int l,int r) {
if (l<=cl and cl<=cr) return tree[c];
int mid=cl+cr>>1;
if (l<=mid and r<=mid) return query(c<<1,cl,mid,l,r);
if (r>mid and l>mid) return query(c<<1|1,mid+1,cr,l,r);
return merge(query(c<<1,cl,mid,l,r),query(c<<1|1,mid+1,cr,l,r),mid-max(l,cl)+1,min(cr,r)-mid);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
std::vector<long long> C;
n = SZ(H);
rep(i,0,n) h[i] = H[i];
init(1,0,n-1);
rep(i,0,SZ(L)) {
pair<int,pii> tmp = query(1,0,n-1,L[i],R[i]);
int ans = (R[i]-L[i]+1)*2 - max(tmp.fi,max(tmp.se.fi,tmp.se.se));
C.pb(ans);
}
return C;
}
