#include <bits/stdc++.h>
using namespace std;
const int c=5002, cc=100002;
vector<long long> sz;
int n, bal[cc], jobb[cc], ert[cc][20];
long long q, maxi[c][c], kom[c][c];
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
n=h.size(), q=l.size();
/*if (n<=5000 && q<=5000) {
for (int i=0; i<n; i++) maxi[i][i]=h[i];
for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) maxi[i][j]=max(maxi[i][j-1], maxi[j][j]);
for (int i=0; i<n; i++) for (int j=0; j<i; j++) maxi[i][j]=maxi[j][i];
for (int i=0; i<n; i++) for (int j=1; j<=n; j++) kom[i][j]=kom[i][j-1]+maxi[i][j-1];
for (int i=0; i<q; i++) {
long long ans=1e18;
for (int j=l[i]; j<=r[i]; j++) {
ans=min(ans, kom[j][r[i]+1]-kom[j][l[i]]);
}
sz.push_back(ans);
}
return sz;
}*/
for (int i=0; i<n; i++) {
if (h[i]==2) {
for (int j=i-1; j>=0 && h[j]==1; j--) jobb[j]=i;
jobb[i]=i;
}
}
for (int i=n-1; i>=0 && h[i]==1; i--) jobb[i]=n;
for (int i=n-1; i>=0; i--) {
if (h[i]==2) {
for (int j=i+1; j<n && h[j]==1; j++) bal[j]=i;
bal[i]=i;
}
}
for (int i=0; i<n && h[i]==1; i++) bal[i]=-1;
for (int i=0; i<n; i++) ert[i][0]=jobb[i]-bal[i]+1;
for (int j=1; j<18; j++) {
for (int i=0; i<n; i++) {
int p=min(n-1, i+(1<<(j-1)));
ert[i][j]=max(ert[i][j-1], ert[p][j-1]);
}
}
for (int i=0; i<q; i++) {
int a=l[i], b=r[i], k=b-a+1, p=0, po=1, db=0;
if (bal[b]<a) p=k;
else {
p=max(jobb[a]-a, b-bal[b]), a=jobb[a], b=bal[b];
while(2*po<=b-a) po*=2, db++;
p=max({p, ert[a][db], ert[b-po+1][db]});
}
sz.push_back(2*k-p);
}
return sz;
}
