#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const ll inf = 1e18;
struct LCT{
struct line{
int k; ll b;
ll operator ()(int x){
return 1LL * k * x + b;
}
};
vector<line> t;
vector<ll> p;
int n;
LCT(int ns){
n = ns;
t.assign(4 * n, {0, inf});
p.resize(4 * n);
}
void apply(int v, ll& x){
t[v].b += x; p[v] += x;
}
void push1(int& v){
if (!p[v]) return;
int vv = 2 * v;
apply(vv, p[v]);
apply(vv + 1, p[v]);
p[v] = 0;
}
void add(int v, int tl, int tr, int& l, int& r, ll& x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
apply(v, x);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v);
add(vv, tl, tm, l, r, x);
add(vv + 1, tm + 1, tr, l, r, x);
}
void add(int l, int r, ll x){
if (l > r) return;
add(1, 1, n, l, r, x);
}
void insert(int v, int tl, int tr, line f){
if (tl == tr){
if (t[v](tl) > f(tl)) t[v] = f;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v);
if (t[v].k > f.k) swap(t[v], f);
if (t[v](tm) > f(tm)){
swap(t[v], f);
insert(vv + 1, tm + 1, tr, f);
}
else {
insert(vv, tl, tm, f);
}
}
void chmin(int v, int tl, int tr, int& l, int& r, line& f){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
insert(v, tl, tr, f);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v);
chmin(vv, tl, tm, l, r, f);
chmin(vv + 1, tm + 1, tr, l, r, f);
}
void chmin(int l, int r, int k, ll b){
if (l > r) return;
line f = {k, b};
chmin(1, 1, n, l, r, f);
}
ll get(int v, int tl, int tr, int& x){
if (tl == tr) return t[v](x);
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v);
if (x <= tm){
return min(t[v](x), get(vv, tl, tm, x));
}
return min(t[v](x), get(vv + 1, tm + 1, tr, x));
}
ll get(int x){
return get(1, 1, n, x);
}
};
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
int n = (int) H.size(), q = (int) L.size();
vector<int> h(n + 1);
for (int i = 1; i <= n; i++){
h[i] = H[i - 1];
}
L.insert(L.begin(), 0); R.insert(R.begin(), 0);
vector<int> log(n + 1);
for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
const int lg = log[n];
vector<vector<pii>> sp(n + 1, vector<pii>(lg + 1));
for (int i = 1; i <= n; i++) sp[i][0] = {h[i], i};
for (int j = 1; j <= lg; j++){
for (int i = 1; i + (1 << j) <= n + 1; i++){
sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
}
auto get = [&](int l, int r){
int k = log[r - l + 1];
return max(sp[l][k], sp[r - (1 << k) + 1][k]);
};
vector<int> g[n + 1], nd(n + 1);
int cc = 0;
function<int(int, int)> build1 = [&](int l, int r){
int p = get(l, r).ss, x = -1, y = -1;
if (p != l) x = build1(l, p - 1);
if (p != r) y = build1(p + 1, r);
nd[p] = ++cc;
if (x != -1) g[cc].pb(x);
if (y != -1) g[cc].pb(y);
return cc;
};
build1(1, n);
vector<vector<int>> pw(n + 1, vector<int>(lg + 1));
vector<int> tin(n + 1), tout(n + 1);
int timer = 0;
function<void(int, int)> fill = [&](int v, int pr){
tin[v] = ++timer;
pw[v][0] = pr;
for (int i = 1; i <= lg; i++){
pw[v][i] = pw[pw[v][i - 1]][i - 1];
}
for (int i: g[v]){
fill(i, v);
}
tout[v] = timer;
};
fill(n, n);
auto check = [&](int x, int y){
return (tin[x] <= tin[y] && tout[x] >= tout[y]);
};
auto lca = [&](int x, int y){
if (check(x, y)) return x;
if (check(y, x)) return y;
for (int i = lg; i >= 0; i--){
if (!check(pw[x][i], y)){
x = pw[x][i];
}
}
return pw[x][0];
};
vector<int> qs[n + 1];
for (int i = 1; i <= q; i++){
L[i]++; R[i]++;
qs[lca(nd[L[i]], nd[R[i]])].pb(i);
}
vector<ll> out(q + 1, inf); cc = 0;
LCT T1(n), T2(n);
for (int i = 1; i <= n; i++){
T1.add(i, i, -inf);
T2.add(i, i, -inf);
}
function<void(int, int)> build = [&](int l, int r){
auto [m, p] = get(l, r);
if (l != p) build(l, p - 1);
if (r != p) build(p + 1, r);
for (int i: qs[++cc]){
out[i] = min(out[i], T2.get(L[i]) + 1LL * m * (R[i] - p + 1));
out[i] = min(out[i], T1.get(R[i]) + 1LL * m * (p - L[i] + 1));
}
// T2[i]' = min(T2[i] + m * (r - p + 1), T2[p + 1] + m * (p - i + 1)); (l <= i < p)
T2.add(l, p, 1LL * m * (r - p + 1));
if (r != p) T2.chmin(l, p, -m, T2.get(p + 1) + 1LL * m * (p + 1));
// T1[i]' = min(T1[i] + m * (p - l + 1), T1[p - 1] + m * (i - p + 1)); (p < i <= r)
T1.add(p, r, 1LL * m * (p - l + 1));
if (l != p) T1.chmin(p, r, m, T1.get(p - 1) - 1LL * m * (p - 1));
};
build(1, n);
vector<ll> ret;
for (int i = 1; i <= q; i++) ret.pb(out[i]);
return ret;
}
