#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=99999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[750009],pas,l,r,z,lft[100009],rgt[100009],F[400009];
long long sub3;
long long seg[400009],za;
pair <long long, long long> Q[750009];
vector <long long> ANS;
long long Lf[5003][5003],Rg[5003][5003];
void read(long long q, long long w, long long rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
if(z<seg[rr]) z=seg[rr];
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
a=H.size();
tes=L.size();
for(i=1; i<=a; i++){
f[i]=H[i-1];
}
for(t=1; t<=tes; t++){
Q[t].first=L[t-1]+1;
Q[t].second=R[t-1]+1;
}
sub3=0;
for(i=1; i<=a; i++){
if(f[i]>2){
sub3=1;
break;
}
}
if(sub3==0){
lft[0]=0;
for(i=1; i<=a; i++){
if(f[i]==2){
lft[i]=i;
}else{
lft[i]=lft[i-1];
}
}
rgt[a+1]=a+1;
for(i=a; i>=1; i--){
if(f[i]==2){
rgt[i]=i;
}else{
rgt[i]=rgt[i+1];
}
}
for(i=1; i<=a; i++){
F[i]=i-lft[i]+rgt[i]-i-1;
if(F[i]<0) F[i]=0;
}
za=1;
while(za<a) za*=2;
for(i=za; i<za+a; i++){
seg[i]=F[i-za+1];
}
for(i=za+a; i<=za*2; i++){
seg[i]=0;
}
for(i=za-1; i>=1; i--){
seg[i]=max(seg[i*2],seg[i*2+1]);
}
for(t=1; t<=tes; t++){
c=rgt[Q[t].first];d=lft[Q[t].second];
if(c>d){
ANS.push_back(Q[t].second-Q[t].first+1);
continue;
}
l=c;r=d;z=0;
read(1,za,1);
z=max(z,c-Q[t].first);
z=max(z,d-Q[t].second);
zx=z+(Q[t].second-Q[t].first+1-z)*2;
ANS.push_back(zx);
}
return ANS;
}
if(a<=5000&&tes<=5000){
for(i=1; i<=a; i++){
zx=0;xc=0;
for(j=i; j>=1; j--){
if(xc<f[j]) xc=f[j];
zx+=xc;
Lf[i][j]=zx;
}
}
for(i=1; i<=a; i++){
zx=0;xc=0;
for(j=i; j<=a; j++){
if(xc<f[j]) xc=f[j];
zx+=xc;
Rg[i][j]=zx;
}
}
for(t=1; t<=tes; t++){
zx=inf;
for(i=Q[t].first; i<=Q[t].second; i++){
if(zx>Lf[i][Q[t].first]+Rg[i][Q[t].second]-f[i]){
zx=Lf[i][Q[t].first]+Rg[i][Q[t].second]-f[i];
}
}
ANS.push_back(zx);
}
return ANS;
}
return ANS;
}
/*int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
vector <int> H,L,R;
cin>>a>>tes;
for(i=1; i<=a; i++){
cin>>c;
H.push_back(c);
}
for(t=1; t<=tes; t++){
cin>>c>>d;
L.push_back(c);
R.push_back(d);
}
ANS=minimum_costs(H,L,R);
for(t=0; t<ANS.size(); t++){
cout<<ANS[t]<<" ";
}
return 0;
}*/
