#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=7.5e5;
int n, q;
vector<int> h;
struct ct {
array<int, 2> st[20][mxN];
int c[mxN][2];
ll ans[mxN];
array<int, 2> qry(int l, int r) {
int k=31-__builtin_clz(r-l+1);
return max(st[k][l], st[k][r-(1<<k)+1]);
}
int bld(int l=0, int r=n-1, int p=-1) {
if(l>r)
return -1;
int u=qry(l, r)[1];
c[u][0]=bld(l, u-1, u);
c[u][1]=bld(u+1, r, u);
ans[u]=min((~c[u][0]?ans[c[u][0]]:0)+(r-u+1ll)*h[u], (~c[u][1]?ans[c[u][1]]:0)+(u-l+1ll)*h[u]);
return u;
}
void init() {
for(int i=0; i<n; ++i)
st[0][i]={h[i], i};
for(int k=1; k<20; ++k)
for(int i=0; i<=n-(1<<k); ++i)
st[k][i]=max(st[k-1][i], st[k-1][i+(1<<k-1)]);
bld();
}
} ct;
struct pch {
int l[mxN], anc[mxN][20];
ll c[mxN], a[mxN], b[mxN];
void init(int x) {
for(int i=0; i<n; ++i) {
l[i]=i-1;
while(~l[i]&&h[l[i]]-x<=h[i])
l[i]=l[l[i]];
c[i]=h[i]*(i-l[i])+(~l[i]?c[l[i]]:0);
a[i]=h[i];
b[i]=(~ct.c[i][x]?ct.ans[ct.c[i][x]]:0)-(i-1ll)*h[i]+c[i];
}
for(int i=0; i<n; ++i) {
anc[i][0]=l[i];
if(~l[i]&&~anc[l[i]][0]&&(b[l[i]]-b[anc[l[i]][0]])/(a[anc[l[i]][0]]-a[l[i]])>(b[i]-b[l[i]])/(a[l[i]]-a[i])) {
for(int k=19; ~k; --k) {
int j=anc[anc[i][0]][k];
if(~j&&~anc[j][0]&&(b[j]-b[anc[j][0]])/(a[anc[j][0]]-a[j])>(b[i]-b[j])/(a[j]-a[i]))
anc[i][0]=j;
}
anc[i][0]=anc[anc[i][0]][0];
}
for(int k=1; k<20; ++k)
anc[i][k]=~anc[i][k-1]?anc[anc[i][k-1]][k-1]:-1;
}
}
ll qry(int s, int t) {
if(s==t)
return 0;
int i=s;
if(anc[i][0]>t&&a[anc[i][0]]*s+b[anc[i][0]]<a[i]*s+b[i]) {
for(int k=19; ~k; --k) {
int j=anc[i][k];
if(~j&&~anc[j][0]&&anc[j][0]>t&&a[anc[j][0]]*s+b[anc[j][0]]<a[j]*s+b[j])
i=j;
}
i=anc[i][0];
}
ll ans=a[i]*s+b[i];
for(int k=19; ~k; --k)
if(~anc[i][k]&&anc[i][k]>t)
i=anc[i][k];
return ans-c[i];
}
} pl, pr;
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
n=h.size(), q=l.size();
::h=h;
ct.init();
pl.init(0);
reverse(::h.begin(), ::h.end());
reverse(ct.c, ct.c+n);
pr.init(1);
vector<ll> ans(q);
for(int i=0; i<q; ++i) {
int w=ct.qry(l[i], r[i])[1];
ll a1=pr.qry(n-1-l[i], n-1-w)+(r[i]-w+1ll)*h[w], a2=pl.qry(r[i], w)+(w-l[i]+1ll)*h[w];
ans[i]=min(a1, a2);
}
return ans;
}
