// In the name of Allah
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = (1 << 20) + 4;
const int maxs = (1 << 21) + 4;
const int maxlg = 20;
const ll oo = 1e18 + 4;
int n, q;
pll A[maxn]; int L[maxn], R[maxn];
pll rmq[maxn][maxlg]; pii Qx[maxn]; vector<ll> ans;
pii Q1[maxn], Q2[maxn]; ll val1[maxn], val2[maxn];
vector<pair<int, pii>> ls; ll dp[maxs];
ll valx[maxn], valr[maxn], vals[maxn], valf[maxn];
vector<int> adj[maxn]; int h[maxn], par[maxn], sz[maxn];
int st[maxn], ft[maxn], timer, hld[maxn]; pll Ax[maxn];
int GI(int l, int r) {
pair<int, pii> x = Mp(r - l, Mp(l, r));
int j = lower_bound(all(ls), x) - ls.begin();
if (j < len(ls) && ls[j] == x) return j;
return -1;
}
void build_rmq() {
for (int i = n - 1; i >= 0; i--) {
rmq[i][0] = A[i];
for (int j = 1; j < maxlg; j++) {
if (i + (1 << j) - 1 >= n) break;
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
}
pll get_max(int l, int r) {
if (l >= r) return Mp(-oo, -1);
int j = __lg(r - l);
return max(rmq[l][j], rmq[r - (1 << j)][j]);
}
void build(int v, int tl, int tr) {
}
ll get_val(int v, int tl, int tr, int l, int r, int x) {
ll res = oo;
for (int i = l; i < r; i++) {
res = min(res, Ax[i].F * x + Ax[i].S);
}
return res;
}
ll getx(int v, int r, int x) {
ll res = oo;
while (h[v] > h[r]) {
int u = hld[v];
if (h[u] > h[r]) {
res = min(res, get_val(0, 0, n + 1, st[u], st[v] + 1, x));
v = par[u];
}
else {
res = min(res, get_val(0, 0, n + 1, st[r] + 1, st[v] + 1, x));
v = r;
}
}
return res;
}
void pre_dfs(int v, int p = -1) {
par[v] = p; sz[v] = 1;
for (int u : adj[v]) {
h[u] = h[v] + 1;
pre_dfs(u, v);
sz[v] += sz[u];
}
}
bool cmp(int i, int j) {
return (sz[i] > sz[j]);
}
void res_dfs(int v, int p = -1) {
st[v] = timer++;
if (p != -1 && st[p] + 1 == st[v]) hld[v] = hld[p];
else hld[v] = v;
sort(all(adj[v]), cmp);
for (int u : adj[v]) {
res_dfs(u, v);
}
ft[v] = timer;
}
void solvex(int T) {
for (int i = 0; i <= n; i++) adj[i].clear();
for (int i = n - 1; i >= 0; i--) {
for (R[i] = i + 1; R[i] != n && A[i] > A[R[i]]; R[i] = R[R[i]]);
}
for (int i = n - 1; i >= 0; i--) {
adj[R[i]].pb(i);
if (R[i] == n) {
valx[i] = A[i].F; valr[i] = A[i].F;
vals[i] = valr[i]; valf[i] = valx[i];
}
else {
ll Rx = (T == 0) ? dp[GI(i, R[i])] : dp[GI(n - R[i] - 1, n - i - 1)];
valx[i] = A[i].F + Rx;
valr[i] = A[i].F * (R[i] - i);
vals[i] = valr[i] + vals[R[i]];
valf[i] = valx[i] + vals[R[i]];
}
valf[i] += A[i].F * i;
}
pre_dfs(n); timer = 0; res_dfs(n);
for (int i = 0; i < n; i++) {
Ax[st[i]] = Mp(-A[i].F, valf[i]);
}
build(0, 0, n + 1);
for (int i = 0; i < q; i++) {
int l = Q1[i].F, r = Q1[i].S;
ans[i] = min(ans[i], val1[i] + getx(l, r, l) - vals[r]);
}
}
vector<ll> minimum_costs(vector<int> Hx, vector<int> Lx, vector<int> Rx) {
n = len(Hx); q = len(Lx);
for (int i = 0; i < n; i++) A[i] = Mp(Hx[i], i);
build_rmq();
for (int i = 0; i < n; i++) {
for (L[i] = i - 1; L[i] != -1 && A[i] > A[L[i]]; L[i] = L[L[i]]);
if (L[i] != -1) ls.pb(Mp(i - L[i], Mp(L[i], i)));
}
for (int i = n - 1; i >= 0; i--) {
for (R[i] = i + 1; R[i] != n && A[i] > A[R[i]]; R[i] = R[R[i]]);
if (R[i] != n) ls.pb(Mp(R[i] - i, Mp(i, R[i])));
}
sort(all(ls)); ls.resize(unique(all(ls)) - ls.begin());
for (int i = 0; i < len(ls); i++) {
int l = ls[i].S.F, r = ls[i].S.S;
if (r - l <= 1) dp[i] = 0;
else {
int j = get_max(l + 1, r).S;
dp[i] = min(dp[GI(l, j)] + A[j].F * (r - j), dp[GI(j, r)] + A[j].F * (j - l));
}
}
for (int i = 0; i < q; i++) {
Qx[i] = Mp(Lx[i], Rx[i] + 1);
int l = Qx[i].F, r = Qx[i].S;
int j = get_max(l, r).S; ans.pb(A[j].F * (r - l));
Q1[i] = Mp(l, j); val1[i] = A[j].F * (r - j);
Q2[i] = Mp(n - r, n - j - 1); val2[i] = A[j].F * (j - l + 1);
}
for (int T = 0; T < 2; T++) {
solvex(T);
reverse(A, A + n);
for (int i = 0; i < q; i++) {
swap(Q1[i], Q2[i]);
swap(val1[i], val2[i]);
}
}
return ans;
}
