#include "meetings.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 750005;
const ll oo = 1e18;
int n, q;
pi st[N][20];
int argmax(int L, int R) { // [L, R]
int k = __lg(R - L + 1);
return max(st[L][k], st[R - (1 << k) + 1][k]).S;
};
ll ans[N];
vi G[N];
namespace segtree {
struct node {
ll l_val, r_val;
ll m, b;
ll lz;
int tl, tr;
node(ll val = 0) {
l_val = r_val = val;
m = b = lz = 0;
}
} t[N * 4];
void pull(int v) {
t[v].l_val = t[v * 2].l_val;
t[v].r_val = t[v * 2 + 1].r_val;
}
void apply_add(int v, ll x) {
t[v].l_val += x, t[v].r_val += x;
if(t[v].m) {
t[v].b += x;
} else {
t[v].lz += x;
}
}
void apply_set(int v, ll m, ll b) {
t[v].l_val = t[v].tl * m + b;
t[v].r_val = (t[v].tr - 1) * m + b;
t[v].m = m, t[v].b = b;
t[v].lz = 0;
}
void push(int v) {
if(t[v].m) { // set
apply_set(v * 2, t[v].m, t[v].b);
apply_set(v * 2 + 1, t[v].m, t[v].b);
t[v].m = t[v].b = 0;
} else { // add
apply_add(v * 2, t[v].lz);
apply_add(v * 2 + 1, t[v].lz);
t[v].lz = 0;
}
}
void build(int v = 1, int tl = 0, int tr = n) {
t[v] = node();
t[v].tl = tl, t[v].tr = tr;
if(tr - tl == 1)
return;
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
}
void add(int l, int r, ll x, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) {
apply_add(v, x);
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) add(l, r, x, v * 2, tl, tm);
if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
pull(v);
}
ll qry(int pos, int v = 1, int tl = 0, int tr = n) {
if(tr - tl == 1)
return t[v].l_val;
push(v);
int tm = (tl + tr) / 2;
if(pos < tm) return qry(pos, v * 2, tl, tm);
else return qry(pos, v * 2 + 1, tm, tr);
}
void cmin(int l, int r, ll m, ll b, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) {
if(t[v].r_val >= m * (tr - 1) + b) {
apply_set(v, m, b);
return;
}
if(t[v].l_val <= m * tl + b)
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) cmin(l, r, m, b, v * 2, tl, tm);
if(r > tm) cmin(l, r, m, b, v * 2 + 1, tm, tr);
pull(v);
}
} // segtree
namespace brute {
int t[N];
void build() {
for(int i = 0; i < n; i++) {
t[i] = 0;
}
}
void add(int l, int r, ll x) {
for(int i = l; i < r; i++)
t[i] += x;
}
void upd(int l, int r, ll m, ll b) {
for(int i = l; i < r; i++)
t[i] = m * i + b;
}
ll qry(int i) {
return t[i];
}
void cmin(int l, int r, ll m, ll b) {
for(int i = l; i < r; i++) {
int now = t[i];
if(m * i + b < now) {
t[i] = m * i + b;
} else {
break;
}
}
}
} // brute
using namespace brute;
// using namespace segtree;
int h[N], l[N], r[N];
void dfs(int L, int R) { // [L, R]
if(L > R) return;
int m = argmax(L, R);
dfs(L, m - 1), dfs(m + 1, R);
for(int i:G[m]) {
ll cur = 1LL * (m - l[i] + 1) * h[m];
if(r[i] > m) cur += qry(r[i]);
ans[i] = min(ans[i], cur);
}
add(m, R + 1, 1LL * (m - L + 1) * h[m]);
if(L < m)
cmin(m, R + 1, h[m], qry(m - 1) - h[m] * (m - 1));
}
pi max2(pi a, pi b) {
if(a.F != b.F) return max(a, b);
return min(a, b);
}
void solve(bool f = false) {
for(int i = 0; i < n; i++)
st[i][0] = {h[i], i};
for(int j = 1; j < 20; j++)
for(int i = 0; i + (1 << j) - 1 < n; i++) {
if(f)
st[i][j] = max2(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
else
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
for(int i = 0; i < q; i++)
G[argmax(l[i], r[i])].PB(i);
build();
dfs(0, n - 1);
for(int i = 0; i < n; i++)
G[i].clear();
}
V<ll> minimum_costs(vi _h, vi _l, vi _r) {
n = SZ(_h), q = SZ(_l);
for(int i = 0; i < n; i++) h[i] = _h[i];
for(int i = 0; i < q; i++) l[i] = _l[i], r[i] = _r[i], ans[i] = oo;
solve();
reverse(h, h + n);
for(int i = 0; i < q; i++) {
swap(l[i], r[i]);
l[i] = n - l[i] - 1, r[i] = n - r[i] - 1;
}
solve(1);
V<ll> tt;
for(int i = 0; i < q; i++)
tt.PB(ans[i]);
return tt;
}
