#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "meetings.h"
#endif
using namespace std;
using ll = long long;
const int p2 = 131072;
const int MAXN = 100000;
int st[p2+p2];
int one_start[MAXN];
int one_end[MAXN];
int RMQ(int l, int r)
{
l += p2;
r += p2;
// if(l>r) swap(l,r);
int ans=0;
while(l<=r)
{
if(l%2 == 1) ans=max(ans,st[l++]);
if(r%2 == 0) ans=max(ans,st[r--]);
l/=2;
r/=2;
}
return ans;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
int n = H.size();
int q = L.size();
// compute one_start[i]
int cur_start = 0;
bool in_seg = 0;
for(int i=0; i<n; i++)
{
if(H[i]!=1)
{
one_start[i]=-1;
in_seg=0;
continue;
}
if(!in_seg)
{
in_seg=1;
cur_start=i;
one_start[i]=i;
}
else
{
one_start[i]=cur_start;
}
}
int cur_end = 0;
in_seg = 0;
for(int i=n-1; i>=0; i--)
{
if(H[i]!=1)
{
one_end[i]=-1;
in_seg=0;
continue;
}
if(!in_seg)
{
in_seg=1;
cur_end=i;
one_end[i]=i;
}
else
{
one_end[i]=cur_end;
}
}
//for(int i=0; i<n; i++) cout << one_start[i] << " ";
//cout << endl;
for(int i=0; i<n; i++)
{
if(one_start[i]!=-1)
{
st[p2+i]=one_end[i]-one_start[i]+1;
}
}
for(int i=p2-1; i>=1; i--)
{
st[i]=max(st[i+i],st[i+i+1]);
}
vector<ll> ans;
for(int i=0; i<q; i++)
{
int cur=0;
if(one_end[L[i]] != -1) cur = max(cur, min(R[i],one_end[L[i]])-L[i]+1);
//if(i>0) cout << cur << endl;
if(one_end[R[i]] != -1) cur = max(cur, R[i]-max(L[i],one_start[R[i]])+1);
//if(i>0) cout << cur << endl;
int left, right;
if(one_end[L[i]]!=-1) left = one_end[L[i]]+1;
else left = L[i];
if(one_end[R[i]]!=-1) right = one_start[R[i]]-1;
else right = R[i];
cur = max(cur,RMQ(left,right));
//if(i>0) cout << cur << endl;
// cout << cur << endl;
//cout << 2*(R[i]-L[i]+1) <<" "<< cur << endl;
ans.push_back(2*(R[i]-L[i]+1) - cur);
}
return ans;
}
#ifdef ARTHUR_LOCAL
int main()
{
// cout << pow(2,17) << endl;
minimum_costs({1,1,2,1},{0,1},{2,3});
}
#endif
