#include"meetings.h"
#define N 750009
#define LG 20
#define lc(i) ((i)<<1|1)
#define rc(i) ((i)+1<<1)
#define int long long
using namespace std;
int n,q,a[N],lg[N],st[LG][N],trek[N<<2],treb[N<<2],lazy[N<<2];
int lft[N<<2],rgt[N<<2];
vector<int>ql[N],qr[N],id[N],ans;
inline int qmx(const int&l,const int&r)
{
int i=lg[r-l];
if(a[st[i][l]]>a[st[i][r-(1<<i)+1]])return st[i][l];
else return st[i][r-(1<<i)+1];
}
inline void pd(const int&i,const int&l,const int&r)
{
if(trek[i]^1<<30)
{
int mid=l+r>>1;
trek[lc(i)]=trek[rc(i)]=trek[i];
treb[lc(i)]=treb[rc(i)]=treb[i];
lazy[lc(i)]=lazy[rc(i)]=0;
lft[lc(i)]=trek[i]*l+treb[i];
rgt[lc(i)]=trek[i]*mid+treb[i];
lft[rc(i)]=trek[i]*(mid+1)+treb[i];
rgt[rc(i)]=trek[i]*r+treb[i];
trek[i]=1<<30;
}
if(lazy[i])
{
lazy[lc(i)]+=lazy[i];
lazy[rc(i)]+=lazy[i];
lft[lc(i)]+=lazy[i];
rgt[lc(i)]+=lazy[i];
lft[rc(i)]+=lazy[i];
rgt[rc(i)]+=lazy[i];
lazy[i]=0;
}
}
inline void push(const int&i,const int&l,const int&r,const int&ql,
const int&qr,const int&k,const int&b)
{
if(qr<l||r<ql)return;
if(ql<=l&&r<=qr)
{
trek[i]=k;treb[i]=b;lazy[i]=0;
lft[i]=k*l+b;
rgt[i]=k*r+b;
return;
}
int mid=l+r>>1;pd(i,l,r);
push(lc(i),l,mid,ql,qr,k,b);
push(rc(i),mid+1,r,ql,qr,k,b);
lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
}
inline int qry(const int&i,const int&l,const int&r,const int&p)
{
if(l==r)return lft[i];
int mid=l+r>>1;pd(i,l,r);
if(p<=mid)return qry(lc(i),l,mid,p);
return qry(rc(i),mid+1,r,p);
}
inline void add(const int&i,const int&l,const int&r,const int&ql,
const int&qr,const int&x)
{
if(qr<l||r<ql)return;
if(ql<=l&&r<=qr){lazy[i]+=x;lft[i]+=x;rgt[i]+=x;return;}
int mid=l+r>>1;pd(i,l,r);
add(lc(i),l,mid,ql,qr,x);add(rc(i),mid+1,r,ql,qr,x);
lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
}
inline int find(const int&i,const int&l,const int&r,const int&ql,
const int&qr,const int&k,const int&b,const bool&dir)
{
if(qr<l||r<ql)return-1;
if(!dir)
{
if(qr>=r&&rgt[i]<=k*r+b)return-1;
if(ql<=l&&lft[i]>k*l+b)return l;
int mid=l+r>>1;pd(i,l,r);
int tmp=find(lc(i),l,mid,ql,qr,k,b,0);
if(~tmp)return tmp;
return find(rc(i),mid+1,r,ql,qr,k,b,0);
}
else
{
if(ql<=l&&lft[i]<=k*l+b)return-1;
if(qr>=r&&rgt[i]>k*r+b)return r;
int mid=l+r>>1;pd(i,l,r);
int tmp=find(rc(i),mid+1,r,ql,qr,k,b,1);
if(~tmp)return tmp;
return find(lc(i),l,mid,ql,qr,k,b,1);
}
}
inline void dfs1(const int&l,const int&r)
{
if(l==r){push(0,0,n-1,l,l,0,a[l]);return;}
int i=qmx(l,r);
if(i==l)
{
dfs1(i+1,r);
push(0,0,n-1,i,i,0,qry(0,0,n-1,i+1)+a[i]);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],a[i]*(qr[i][j]-i+1));
return;
}
if(i==r)
{
dfs1(l,i-1);
push(0,0,n-1,i,i,0,0);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],qry(0,0,n-1,ql[i][j])+a[i]);
add(0,0,n-1,l,i,a[i]);
return;
}
dfs1(l,i-1);dfs1(i+1,r);
push(0,0,n-1,i,i,0,0);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],
qry(0,0,n-1,ql[i][j])+a[i]*(qr[i][j]-i+1));
push(0,0,n-1,i,i,0,qry(0,0,n-1,i+1)+a[i]);
add(0,0,n-1,l,i-1,a[i]*(r-i+1));
int k=-a[i],b=qry(0,0,n-1,i)+a[i]*i;
int x=find(0,0,n-1,l,i-1,k,b,0);
if(~x)push(0,0,n-1,x,i-1,k,b);
}
inline void dfs2(const int&l,const int&r)
{
if(l==r){push(0,0,n-1,l,l,0,a[l]);return;}
int i=qmx(l,r);
if(i==l)
{
dfs2(i+1,r);
push(0,0,n-1,i,i,0,0);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],qry(0,0,n-1,qr[i][j])+a[i]);
add(0,0,n-1,i,r,a[i]);
return;
}
if(i==r)
{
dfs2(l,i-1);
push(0,0,n-1,i,i,0,qry(0,0,n-1,i-1)+a[i]);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],a[i]*(i-ql[i][j]+1));
return;
}
dfs2(l,i-1);dfs2(i+1,r);
push(0,0,n-1,i,i,0,0);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],
qry(0,0,n-1,qr[i][j])+a[i]*(i-ql[i][j]+1));
push(0,0,n-1,i,i,0,qry(0,0,n-1,i-1)+a[i]);
add(0,0,n-1,i+1,r,a[i]*(i-l+1));
int k=a[i],b=qry(0,0,n-1,i)-a[i]*i;
int x=find(0,0,n-1,i+1,r,k,b,1);
if(~x)push(0,0,n-1,i+1,x,k,b);
}
vector<int>minimum_costs(vector<signed>H,vector<signed>L,vector<signed>R)
{
n=H.size();q=L.size();ans.resize(q);
for(int i=0;i<n;a[i]=H[i],++i);
for(int i=2;i<n;lg[i]=lg[i>>1]+1,++i);
for(int i=n-1;i>=0;--i)
{
st[0][i]=i;
for(int j=1;j<LG;++j)
if(i+(1<<j-1)<n)
if(a[st[j-1][i]]>a[st[j-1][i+(1<<j-1)]])
st[j][i]=st[j-1][i];
else st[j][i]=st[j-1][i+(1<<j-1)];
else st[j][i]=st[j-1][i];
}
for(int i=0,u,v,w;i<q;++i)
{
u=L[i],v=R[i],w=qmx(u,v);
if(u==v){ans[i]=a[u];continue;}
ql[w].emplace_back(u),qr[w].emplace_back(v),
id[w].emplace_back(i);ans[i]=1ll<<60;
}
for(int i=0;i<N<<2;trek[i++]=1<<30);
dfs1(0,n-1);
for(int i=0;i<N<<2;trek[i++]=1<<30);
dfs2(0,n-1);
return ans;
}
