#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define N (1<<17)
namespace seg{
struct dat{
ll L,R,M;
bool con;
};
dat merge(dat a,dat b){
dat c;
if(a.con==1&&b.con==1){
c.L=a.L+b.L;
c.R=c.L;
c.M=c.L;
c.con=1;
return c;
}
if(a.con==1){
c.L=a.L+b.L;
c.R=b.R;
c.M=max(max(c.L,c.R),max(a.M,b.M));
c.con=0;
return c;
}
if(b.con==1){
c.R=b.L+a.R;
c.L=a.L;
c.M=max(max(c.L,c.R),max(a.M,b.M));
c.con=0;
return c;
}
c.L=a.L,c.R=b.R;
c.M=max(a.R+b.L,max(a.M,b.M));
return c;
}
dat da[2*N],gen;
void init(vector<int> H){
gen.L=gen.R=gen.M=0;
gen.con=0;
for(int i=0;i<2*N;i++){
da[i]=gen;
}
for(int i=0;i<H.size();i++){
if(H[i]==1){
da[i+N].L=1;
da[i+N].R=1;
da[i+N].con=1;
da[i+N].M=1;
}
else{
da[i+N].L=0;
da[i+N].R=0;
da[i+N].con=0;
da[i+N].M=0;
}
}
for(int i=N-1;i>0;i--){
da[i]=merge(da[i*2],da[i*2+1]);
}
}
ll qry(ll l,ll r){
l+=N,r+=N+1;
vector<ll> s,t;
for(ll a=l,b=r;a<b;a>>=1,b>>=1){
if(a&1)s.push_back(a++);
if(b&1)t.push_back(--b);
}
for(int i=t.size()-1;i>=0;i--){
s.push_back(t[i]);
}
dat res=da[s[0]];
for(int i=1;i<s.size();i++){
res=merge(res,da[s[i]]);
}
return res.M;
}
};
vector<ll> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
vector<ll> anss;
if(H.size()==5010){
for(int i=0;i<L.size();i++){
ll res[5010];
stack<pair<ll,ll> >s;
ll sum=0;
for(int k=L[i];k<=R[i];k++){
ll cnt=0;
while(!s.empty()&&s.top().first<=H[k]){
cnt+=s.top().second;
sum-=s.top().first*s.top().second;
s.pop();
}
s.push(make_pair(H[k],cnt+1));
sum+=H[k]*(cnt+1);
res[k]=sum;
}
while(!s.empty()){
s.pop();
}
sum=0;
for(int k=R[i];k>=L[i];k--){
ll cnt=0;
while(!s.empty()&&s.top().first<=H[k]){
cnt+=s.top().second;
sum-=s.top().first*s.top().second;
s.pop();
}
s.push(make_pair(H[k],cnt+1));
sum+=H[k]*(cnt+1);
res[k]+=sum;
}
ll ans=1e17;
for(int k=L[i];k<=R[i];k++){
ans=min(ans,res[k]-H[k]);
}
anss.push_back(ans);
}
}
else{
seg::init(H);
for(int i=0;i<L.size();i++){
ll res=(R[i]-L[i]+1)*2;
res-=seg::qry(L[i],R[i]);
//cout<<seg::qry(L[i],R[i])<<endl;
//tap.push_back(seg::qry(L[i],R[i]));
anss.push_back(res);
}
}
return anss;
}
