#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 seg[400010];
void update(int a,int b,int c,int x,int y){
if(seg[c]==b-a+1)return;
if(a==b){
seg[c]=max(seg[c],y-x+1);
return;
}
int m=(a+b)/2;
if(y<=m)update(a,m,2*c,x,y);
else if(x>m)update(m+1,b,2*c+1,x,y);
else {
update(a,m,2*c,x,m);
update(m+1,b,2*c+1,m+1,y);
}
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);
else return max(findseg(a,m,2*c,x,m),findseg(m+1,b,2*c+1,m+1,y));
}
vector<ll> SUB_3(vector<int> L,vector<int> R) {
memset(seg,0,sizeof(seg));
int cur=-1;
for(int i=0;i<n;i++){
if(hei[i]==2){
if(cur+1<=i-1)update(0,n-1,1,cur+1,i-1);
cur=i;
}
}
if(cur+1<=n-1)update(0,n-1,1,cur+1,n-1);
vector<ll> C;
for(int i=0;i<q;i++){
int ones=findseg(0,n-1,1,L[i],R[i]);
ll val=ones+2*(R[i]-L[i]+1-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);
}
