#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=750050;
const int M=2*N;
const ll inf=1e18;
int n,q;
int l[N],r[N],h[N];
ll ans[N];
struct LiChaoSegmentTree
{
struct Line
{
ll k,n;
Line(){ k=n=0;}
Line(ll a, ll b):k(a),n(b){}
ll Get(ll x){ return k*x+n;}
} line[M];
int ls[M],rs[M],tsz,root;
ll lzy[M];
LiChaoSegmentTree(){}
void Build(int &c, int ss, int se)
{
c=++tsz;lzy[c]=0;line[c]=Line(0,inf);
if(ss==se){ line[c]=Line();return;}
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
}
void Build(){ Build(root,1,n);}
void upd(int c, ll f)
{
line[c].n+=f;
lzy[c]+=f;
}
void push(int c)
{
if(lzy[c])
{
upd(ls[c],lzy[c]);
upd(rs[c],lzy[c]);
lzy[c]=0;
}
}
void Add(int c, int ss, int se, int qs, int qe, ll f)
{
if(qs>qe || qs>se || ss>qe) return;
if(qs<=ss && qe>=se){ upd(c,f);return;}
push(c);
int mid=ss+se>>1;
Add(ls[c],ss,mid,qs,qe,f);
Add(rs[c],mid+1,se,qs,qe,f);
}
void Add(int l, int r, ll f){ Add(root,1,n,l,r,f);}
void Set(int c, int ss, int se, int qs, int qe, Line k)
{
if(qs>qe || qs>se || ss>qe) return;
if(qs<=ss && qe>=se)
{
ll A=k.Get(ss),B=line[c].Get(ss),C=k.Get(se),D=line[c].Get(se);
if(A<=B && C<=D){ line[c]=k;return;}
if(A>=B && C>=D) return;
push(c);
int mid=ss+se>>1;
if(A<=B) swap(line[c],k);
if(line[c].Get(mid)<=k.Get(mid)) Set(rs[c],mid+1,se,qs,qe,k);
else swap(line[c],k),Set(ls[c],ss,mid,qs,qe,k);
return;
}
push(c);
int mid=ss+se>>1;
Set(ls[c],ss,mid,qs,qe,k);
Set(rs[c],mid+1,se,qs,qe,k);
}
void Set(int l, int r, ll b, ll a){ Set(root,1,n,l,r,Line(a,b));}
ll Get(int c, int ss, int se, int qi)
{
ll ans=line[c].Get(qi);
if(ss==se) return ans;
push(c);
int mid=ss+se>>1;
if(qi<=mid) return min(ans,Get(ls[c],ss,mid,qi));
else return min(ans,Get(rs[c],mid+1,se,qi));
}
ll Get(int qi){ return Get(root,1,n,qi);}
} FW,BW;
struct SegmentTree
{
int mx[M];
void init(){ for(int i=1;i<M;i++) mx[i]=0;}
int my_max(int x, int y){ return mp(h[x],x)>mp(h[y],y)?x:y;}
void Build()
{
for(int i=n+N;i>=N;i--) mx[i]=i-N;
for(int i=N-1;i;i--) mx[i]=my_max(mx[i<<1],mx[i<<1|1]);
}
int Get(int l, int r)
{
int ans=0;
for(l+=N,r+=N;l<=r;l>>=1,r>>=1)
{
if(l%2==1) ans=my_max(ans,mx[l++]);
if(r%2==0) ans=my_max(ans,mx[r--]);
}
return ans;
}
} RMQ;
vector<int> Qs[N];
void Solve(int l, int r)
{
if(l>r) return;
int m=RMQ.Get(l,r);
Solve(l,m-1);Solve(m+1,r);
for(int i:Qs[m]) ans[i]=min(FW.Get(::r[i])+(ll)h[m]*(m-::l[i]+1),BW.Get(::l[i])+(ll)h[m]*(::r[i]-m+1));
FW.Add(m,r,(ll)h[m]*(m-l+1));
if(m!=l) FW.Set(m,r,FW.Get(m-1)-(ll)h[m]*(m-1),h[m]);
BW.Add(l,m,(ll)h[m]*(r-m+1));
if(m!=r) BW.Set(l,m,BW.Get(m+1)+(ll)h[m]*(m+1),-h[m]);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
n=H.size();q=L.size();
for(int i=1;i<=n;i++) h[i]=H[i-1];
for(int i=1;i<=q;i++) l[i]=L[i-1]+1,r[i]=R[i-1]+1;
RMQ.Build();
for(int i=1;i<=q;i++) Qs[RMQ.Get(l[i],r[i])].pb(i);
FW.Build();BW.Build();
Solve(1,n);
vector<ll> ret;
for(int i=1;i<=q;i++) ret.pb(ans[i]);
return ret;
}
