#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define QAQ
using namespace std;
const int N = 7.5e5 + 7, M = 1 << 24;
const ll inf = 1e18;
struct RMQ {
int a[N], mx[20][N], lg[N];
void init (int n) {
L(i, 2, n) lg[i] = lg[i >> 1] + 1;
L(i, 1, n) mx[0][i] = i;
L(i, 1, 19)
L(j, 1, n - (1 << i) + 1)
mx[i][j] = a[mx[i - 1][j]] > a[mx[i - 1][j + (1 << (i - 1))]] ?
mx[i - 1][j] : mx[i - 1][j + (1 << (i - 1))];
}
inline int queryp (int l, int r) {
int p = lg[r - l + 1];
return a[mx[p][l]] > a[mx[p][r - (1 << p) + 1]] ?
mx[p][l] : mx[p][r - (1 << p) + 1];
}
inline int query (int l, int r) { return a[queryp (l, r)]; }
} a;
int n, q;
map < pair < int, int >, ll > mp;
int h[N];
ll DFS (int l, int r) {
if (l > r) return 0;
if (mp.count({l, r})) return mp[{l, r}];
if (l == r) return h[l];
int mi = a.queryp(l, r);
return mp[{l, r}] = min(DFS(l, mi - 1) + (ll) (r - mi + 1) * h[mi],
DFS(mi + 1, r) + (ll) (mi - l + 1) * h[mi]);
}
struct wk {
bool op;
inline int gmx(int l, int r) {
return op ? n - a.queryp(n - r + 1, n - l + 1) + 1 : a.queryp (l, r);
}
int h[N], stk[N], tp, fa[N], dep[N];
ll fw[N], all[N];
vi e[N];
int dfn[N], MP[N], hv[N], siz[N], mxto[N], idt;
struct line {
int k;
ll b;
line (int K = 0, ll B = 0) {
k = K, b = B;
}
inline ll get (int w) {
return b + (ll) k * w;
}
};
ll inter (line u, line v) {
return (u.b - v.b) / (v.k - u.k);
}
int hd[1 << 21], ch[M][2], tot, seg[M];
line f[N];
void Add(int &id, int L, int R, int p) {
ll nl = f[seg[id]].get(L), nr = f[seg[id]].get(R), pl = f[p].get(L), pr = f[p].get(R);
if(id && nl <= pl && nr <= pr) return;
int x = ++tot;
ch[x][0] = ch[id][0], ch[x][1] = ch[id][1], seg[x] = seg[id];
if(!id || (nl >= pl && nr >= pr)) return seg[x] = p, id = x, void();
id = x;
int mid = (L + R) >> 1;
ll it = inter(f[seg[x]], f[p]);
if(it <= mid) {
if(nl <= pl) Add(ch[x][0], L, mid, seg[x]), seg[x] = p;
else Add(ch[x][0], L, mid, p);
}
else {
if(nl <= pl) Add(ch[x][1], mid + 1, R, p);
else Add(ch[x][1], mid + 1, R, seg[x]), seg[x] = p;
}
}
ll Qry(int id, int L, int R, int pos) {
if(!id) return inf;
if(L == R) return f[seg[id]].get(pos);
int mid = (L + R) >> 1;
if(pos <= mid) return min(f[seg[id]].get(pos), Qry(ch[id][0], L, mid, pos));
else return min(f[seg[id]].get(pos), Qry(ch[id][1], mid + 1, R, pos));
}
int merge (int x, int y, int L, int R) {
if(!x || !y) return x | y;
int nw = ++tot, mid = (L + R) >> 1;
ch[nw][0] = merge(ch[x][0], ch[y][0], L, mid);
ch[nw][1] = merge(ch[x][1], ch[y][1], mid + 1, R);
seg[nw] = seg[x];
Add (nw, L, R, seg[y]);
return nw;
}
void Build (int x, int L, int R) {
if(L == R)
return f[L] = line (-h[MP[L]], fw[MP[L]]), hd[x] = ++tot, seg[hd[x]] = L, void ();
int mid = (L + R) >> 1;
Build (x << 1, L, mid);
Build (x << 1 | 1, mid + 1, R);
hd[x] = merge (hd[x << 1], hd[x << 1 | 1], 1, n);
}
ll query (int x, int L, int R, int l, int r, int p) {
if(l <= L && R <= r) return Qry (hd[x], 1, n, p);
int mid = (L + R) >> 1;
ll ret = inf;
if(l <= mid) ret = min(ret, query (x << 1, L, mid, l, r, p));
if(r > mid) ret = min(ret, query (x << 1 | 1, mid + 1, R, l, r, p));
return ret;
}
void dfs (int x) {
siz[x] = 1;
for (auto v : e[x]) {
dep[v] = dep[x] + 1, dfs(v), siz[x] += siz[v];
if(siz[v] > siz[hv[x]]) hv[x] = v;
}
}
void dfs2(int x) {
dfn[x] = ++idt;
MP[idt] = x;
if(hv[x]) mxto[hv[x]] = mxto[x], dfs2 (hv[x]);
for (auto v : e[x]) if(v != hv[x]) mxto[v] = v, dfs2 (v);
}
void init () {
L(i, 1, n) {
while (tp > 0 && h[i] >= h[stk[tp]] + op) fa[stk[tp]] = i, -- tp;
stk[++tp] = i;
}
R(i, n, 1) if(fa[i])
all[i] = (ll) (fa[i] - i) * h[i] + all[fa[i]],
fw[i] = (op ? DFS(n - (fa[i] - 1) + 1, n - i + 1) : DFS(i, fa[i] - 1)) + all[fa[i]];
L(i, 1, n) fw[i] += (ll) h[i] * i;
L(i, 1, n) if(fa[i]) e[fa[i]].push_back(i);
R(i, n, 1) if(!dfn[i]) dfs (i), mxto[i] = i, dfs2 (i);
Build (1, 1, n);
}
ll query (int l, int r) { // r : max
if(l == r) return 0;
ll ns = 1e18;
int u = l;
for (; mxto[u] != mxto[r]; u = fa[mxto[u]])
ns = min(ns, query (1, 1, n, dfn[mxto[u]], dfn[u], l));
if(dfn[r] < dfn[u]) ns = min(ns, query (1, 1, n, dfn[r] + 1, dfn[u], l));
// for (int u = l; u != r; u = fa[u]) ns = min(ns, fw[u] - (ll) h[u] * l);
return ns - all[r];
}
} u, v;
vector < ll > minimum_costs (vi H, vi L, vi R) {
n = sz(H), q = sz(L);
L(i, 1, n) h[i] = H[i - 1], u.h[i] = v.h[n - i + 1] = h[i], a.a[i] = h[i];
a.init(n);
v.op = true;
u.init(), v.init();
vector < ll > ns (q);
L(t, 0, q - 1) {
int l = L[t], r = R[t];
++ l, ++ r;
int p = a.queryp(l, r);
ns[t] = min(u.query(l, p) + (ll) h[p] * (r - p + 1),
v.query(n - r + 1, n - p + 1) + (ll) h[p] * (p - l + 1));
}
return ns;
}
