#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
int N,Q,L[100000],R[100000],tree[1<<18];
int calc(int l,int r){
int a=0;
l+=1<<17;
r+=1<<17;
while(l<=r){
a=max({a,tree[l],tree[r]});
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
vector<long long> minimum_costs(vector<int>H,vector<int>QL,vector<int>QR){
N=H.size();
Q=QL.size();
for(int i=1;i<N;i++){
if(H[i-1]==1&&H[i]==1){
L[i]=L[i-1];
}
else{
L[i]=i;
}
}
R[N-1]=N-1;
for(int i=N-2;i>=0;i--){
if(H[i]==1&&H[i+1]==1){
R[i]=R[i+1];
}
else{
R[i]=i;
}
}
for(int i=0;i<N;i++){
if(H[i]==1){
tree[i+(1<<17)]=R[i]-L[i]+1;
}
}
for(int i=(1<<17)-1;i;i--){
tree[i]=max(tree[i+i],tree[i+i+1]);
}
vector<long long>res(Q);
for(int _=0;_<Q;_++){
int t=0;
int l,r;
if(H[QL[_]]==1){
t=max(t,min(R[QL[_]],QR[_])-QL[_]+1);
l=R[QL[_]]+1;
}
else{
l=QL[_];
}
if(H[QR[_]]==1){
t=max(t,QR[_]-max(L[QR[_]],QL[_])+1);
r=L[QR[_]]-1;
}
else{
r=QR[_];
}
t=max(t,calc(l,r));
res[_]=2*(QR[_]-QL[_]+1)-t;
}
return res;
}
