#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int nx=750005, kx=20;
int n, q, h[nx], ql[nx], qr[nx], l[nx], r[nx], rt, lvl[nx], pa[nx][kx], mn[nx], mx[nx];
vector<int> qrs[nx];
vector<ll> res;
struct line
{
ll m, c;
line(ll m=0, ll c=1e18): m(m), c(c){}
ll val(ll x) {return m*x+c;}
};
struct lichaotree
{
line d[4*nx];
ll lz[4*nx];
void pushlz(int l, int r, int i)
{
d[i].c+=lz[i];
if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
lz[i]=0;
}
void update(int l, int r, int i, int ql, int qr, line x)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
int md=(l+r)/2;
if (ql<=l&&r<=qr)
{
if (x.val(md)<d[i].val(md)) swap(x, d[i]);
if (d[i].val(l)>x.val(l)) update(l, md, 2*i, ql, qr, x);
if (d[i].val(r)>x.val(r)) update(md+1, r, 2*i+1, ql, qr, x);
}
else
{
update(l, md, 2*i, ql, qr, x);
update(md+1, r, 2*i+1, ql, qr, x);
}
}
void update2(int l, int r, int i, int ql, int qr, ll vl)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
int md=(l+r)/2;
update2(l, md, 2*i, ql, qr, vl);
update2(md+1, r, 2*i+1, ql, qr, vl);
}
ll query(int l, int r, int i, int idx)
{
pushlz(l, r, i);
if (l==r) return d[i].val(idx);
int md=(l+r)/2;
if (idx<=md) return min(d[i].val(idx), query(l, md, 2*i, idx));
else return min(d[i].val(idx), query(md+1, r, 2*i+1, idx));
}
} sl, sr;
void dfs(int u, int p)
{
mn[u]=mx[u]=u;
lvl[u]=lvl[p]+1;
pa[u][0]=p;
for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
if (l[u]) dfs(l[u], u), mn[u]=mn[l[u]];
if (r[u]) dfs(r[u], u), mx[u]=mx[r[u]];
}
int lca(int u, int v)
{
if (lvl[u]>lvl[v]) swap(u, v);
for (int i=kx-1; i>=0; i--) if (lvl[u]<=lvl[pa[v][i]]) v=pa[v][i];
if (u==v) return u;
for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
return pa[u][0];
}
void dfs2(int u)
{
if (l[u]) dfs2(l[u]);
if (r[u]) dfs2(r[u]);
sl.update(1, n, 1, u, u, line(0, 0));
sr.update(1, n, 1, u, u, line(0, 0));
for (auto idx:qrs[u]) res[idx]=min(sl.query(1, n, 1, ql[idx])+(ll)(qr[idx]-u+1)*h[u], sr.query(1, n, 1, qr[idx])+(ll)(u-ql[idx]+1)*h[u]);
sl.update2(1, n, 1, mn[u], u, (ll)(mx[u]-u+1)*h[u]);
if (u!=mx[u]) sl.update(1, n, 1, mn[u], u, line(-h[u], sl.query(1, n, 1, u+1)+((ll)(u+1))*h[u]));
sr.update2(1, n, 1, u, mx[u], (ll)(u-mn[u]+1)*h[u]);
if (u!=mn[u]) sr.update(1, n, 1, u, mx[u], line(h[u], sr.query(1, n, 1, u-1)-((ll)(u-1))*h[u]));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
n=H.size();
q=L.size();
res.resize(q);
for (int i=1; i<=n; i++) h[i]=H[i-1];
for (int i=0; i<q; i++) ql[i]=L[i]+1, qr[i]=R[i]+1;
stack<int> s;
for (int i=1; i<=n; i++)
{
while (!s.empty()&&h[s.top()]<h[i]) l[i]=s.top(), s.pop();
if (!s.empty()) r[s.top()]=i;
else rt=i;
s.push(i);
}
//for (int i=1; i<=n; i++) cout<<"cartesian "<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
dfs(rt, rt);
for (int i=0; i<q; i++) qrs[lca(ql[i], qr[i])].push_back(i); //cout<<"debug "<<i<<' '<<ql[i]<<' '<<qr[i]<<' '<<lca(ql[i], qr[i])<<'\n';
dfs2(rt);
return res;
}
