#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push
typedef long long ll;
int n,q;
vector<ll> hei;
vector<ll> SUB_1_2(vector<int> L,vector<int> R) {
vector<ll> C;
for(int h=0;h<q;h++){
ll ans=INT64_MAX;
ll vall[n],valr[n];
vector<int> v;
ll cur=hei[L[h]];vall[L[h]]=cur;
v.PB(L[h]);
for(int i=L[h]+1;i<=R[h];i++){
while(!v.empty()){
int last=v.back();
if(hei[last]>=hei[i])break;
v.pop_back();
if(v.empty())cur+=(hei[i]-hei[last])*(last-L[h]+1);
else cur+=(hei[i]-hei[last])*(last-v.back());
}
v.PB(i);cur+=hei[i];
vall[i]=cur;
}
v.clear();
cur=hei[R[h]];valr[R[h]]=cur;
v.PB(R[h]);
for(int i=R[h]-1;i>=L[h];i--){
while(!v.empty()){
int last=v.back();
if(hei[last]>=hei[i])break;
v.pop_back();
if(v.empty())cur+=(hei[i]-hei[last])*(R[h]-last+1);
else cur+=(hei[i]-hei[last])*(v.back()-last);
}
v.PB(i);cur+=hei[i];
valr[i]=cur;
}
for(int i=L[h];i<=R[h];i++){
ans=min(ans,vall[i]+valr[i]-hei[i]);
}
C.PB(ans);
}
return C;
}
int pref[400010],suff[400010],seg[400010];
void buildseg(int a,int b,int c){
if(a==b){
if(hei[a]==1){
seg[c]=pref[c]=suff[c]=1;
}
else{
seg[c]=pref[c]=suff[c]=0;
}
return;
}
int m=(a+b)/2;
buildseg(a,m,2*c);
buildseg(m+1,b,2*c+1);
seg[c]=max({seg[2*c],seg[2*c+1],suff[2*c]+pref[2*c+1]});
pref[c]=pref[2*c];
if(pref[2*c]==m-a+1)pref[c]+=pref[2*c+1];
suff[c]=suff[2*c+1];
if(suff[2*c+1]==b-m)suff[c]+=suff[2*c];
return;
}
int findseg(int a,int b,int c,int x,int y){
if(a==x && b==y)return seg[c];
int m=(a+b)/2;
if(y<=m)return findseg(a,m,2*c,x,y);
else if(x>m)return findseg(m+1,b,2*c+1,x,y);
int merge=min(pref[2*c+1],y-m)+min(suff[2*c],m-x+1);
return max({findseg(a,m,2*c,x,m),findseg(m+1,b,2*c+1,m+1,y),merge});
}
vector<ll> SUB_3(vector<int> L,vector<int> R) {
memset(seg,0,sizeof(seg));
buildseg(0,n-1,1);
vector<ll> C;
for(int i=0;i<q;i++){
int all=R[i]-L[i]+1;
int ones=findseg(0,n-1,1,L[i],R[i]);
ll val=ones+2*(all-ones);
C.PB(val);
}
return C;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
n=H.size();q=L.size();
for(int i=0;i<n;i++)hei.PB((ll)H[i]);
if(n<=5000 && q<=5000)return SUB_1_2(L,R);
else return SUB_3(L,R);
}
