#include "meetings.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pll;
const ll Inf = 1e18;
const int N = 75e4 + 10;
int n, q;
vector<int> H, L, R;
ll ans[N];
ll val_l[N * 3], val_r[N * 3];
pll lz[N * 3];
inline void Apply(int id, pll &X, int L, int R){
if(X.F){
val_l[id] = 1ll * L * X.F;
val_r[id] = 1ll * (R - 1) * X.F;
lz[id] = {X.F, 0};
}
val_l[id] += X.S;
val_r[id] += X.S;
lz[id].S += X.S;
}
inline void Shift(int id, int L, int R){
int mid = (L + R) >> 1;
int lc = id << 1, rc = id << 1 | 1;
if(lz[id].F){
val_l[lc] = val_l[id]; //1ll * L * lz[id].F;
val_r[lc] = ( val_l[rc] = 1ll * mid * (lz[id].F) ) - lz[id].F;
val_r[rc] = val_r[id]; //1ll * (R - 1) * lz[id].F;
lz[lc] = lz[rc] = lz[id];
// val_l[lc] += lz[id].S;
val_r[lc] += lz[id].S;
val_l[rc] += lz[id].S;
// val_r[rc] += lz[id].S;
// lz[lc].S += lz[id].S;
// lz[rc].S += lz[id].S;
} else {
val_l[lc] += lz[id].S;
val_r[lc] += lz[id].S;
val_l[rc] += lz[id].S;
val_r[rc] += lz[id].S;
lz[lc].S += lz[id].S;
lz[rc].S += lz[id].S;
}
// Apply(id << 1, lz[id], L, mid);
// Apply(id<<1|1, lz[id], mid, R);
lz[id] = {0, 0};
}
void Add(int id, int l, int r, pll X, int L, int R){
if(r <= L || R <= l) return ;
if(l <= L && R <= r){
if((!X.F) || (1ll * (R - 1) * X.F + X.S <= val_r[id])){
Apply(id, X, L, R);
return ;
} else if(val_l[id] <= 1ll * L * X.F + X.S){
return;
}
}
int mid = (L + R) >> 1;
Shift(id, L, R);
Add(id << 1, l, r, X, L, mid);
Add(id<<1|1, l, r, X, mid, R);
val_l[id] = val_l[id << 1];
val_r[id] = val_r[id<<1|1];
}
ll Get(int id, int idx, int L, int R){
if(L + 1 == R) return val_l[id];
int mid = (L + R) >> 1;
Shift(id, L, R);
if(idx < mid)
return Get(id << 1, idx, L, mid);
return Get(id << 1 | 1, idx, mid, R);
}
// void Build(int id, int L, int R){
// seg[id].r = R - 1;
// if(L + 1 == R) return ;
// int mid = (L + R) >> 1;
// Build(id << 1, L, mid);
// Build(id<<1|1, mid, R);
// }
// int BS(int id, int l, int r, pll ln, int L, int R){
// if(r <= L || R <= l) return R;
// int mid = (L + R) >> 1;
// if(l <= L && R <= r){
// if(seg[id].val_r > 1ll * seg[id].r * ln.F + ln.S)
// return R;
// if(L + 1 == R)
// return L;
// Shift(id);
// int res = BS(id << 1, l, r, ln, L, mid);
// if(res < mid)
// return res;
// return BS(id << 1| 1, l, r, ln, mid, R);
// }
// Shift(id);
// int res = BS(id << 1, l, r, ln, L, mid);
// if(res < mid)
// return res;
// return BS(id<<1|1, l, r, ln, mid, R);
// }
int par[N], sz[N];
ll dp[N];
int Find(int u){
if(par[u] == u) return u;
return par[u] = Find(par[u]);
}
void Merge(int u, int v, ll md){
u = Find(u);
v = Find(v);
// cerr << "^^ " << sz[u] << ' ' << sz[v] << '\n';
// assert(u < v);
// phase 1
Add(1, v - sz[v] + 1, v + 1, {0, 1ll * sz[u] * md}, 0, n + 1);
// cerr << "!! " << 1ll * sz[u] * md << '\n';
// for(int i = v - sz[v] + 1; i <= v; i++){
// cerr << "&& " << Get(1, i, 0, n + 1) << '+' << 1ll*sz[u]*md << '=';
// Add(1, i, i + 1, 1ll * sz[u] * md, 0, n + 1);
// cerr << Get(1, i, 0, n + 1) << '\n';
// if(Get(1, i, 0, n + 1) == 3){
// cerr << "pr : ";
// for(int i = n; i >= 0; i--)
// cerr << Get(1, i, 0, n + 1) << ' ';
// cerr << '\n';
// }
// }
// dp[i] += 1ll * sz[u] * md;
// phase 2
ll vl_u = dp[u];//sz[u] == 0 ? 0 : Get(1, u, 0, n + 1);
Add(1, v - sz[v] + 1, v + 1, {md, vl_u - u * md}, 0, n + 1);
dp[v] = min(dp[v] + 1ll * sz[u] * md, vl_u + 1ll * (v - u) * md);
// int lw = v - sz[v], hg = v + 1;
// int bin_s = BS(1, lw + 1, hg, pll(md, vl_u - u * md), 0, n + 1);
// while(lw + 1 < hg){
// mid = (lw + hg) >> 1;
// ll vl = Get(1, mid, 0, n + 1);
// if(vl > vl_u + md * (mid - u))
// lw = mid;
// else
// hg = mid;
// }
// if(bin_s == n + 1)
// bin_s = v + 1;
// cerr << "! " << bin_s << ' ' << hg << '\n';
// assert(bin_s == hg);
// _ln = pll(md, vl_u - u * md);
// Add_Line(1, v - sz[v] + 1, bin_s, 0, n + 1);
// for(int i = v - sz[v] + 1; i <= v; i++){
// ll vl = Get(1, i, 0, n + 1);
// if(vl > vl_u + md * (i - u))
// Add(1, i, i + 1, pll(0, vl_u + md * (i - u)), 0, n + 1);
// // dp[i] =dp[u] + md * (i - u);
// else
// break;
// }
sz[v] += sz[u];
par[u] = v;
}
vector<int> Q[N];
pii A[N];
pii sg[N << 2];
void BB(int id, int L, int R){
if(L + 1 == R){
sg[id] = A[L];
return ;
}
int mid = (L + R) >> 1;
BB(id << 1, L, mid);
BB(id<<1|1, mid, R);
sg[id] = max(sg[id << 1], sg[id << 1 | 1]);
}
pii GT(int id, int l, int r, int L, int R){
if(r <= L || R <= l) return pii(-1, -1);
if(l <= L && R <= r) return sg[id];
int mid = (L + R) >> 1;
return max(GT(id << 1, l, r, L, mid), GT(id << 1|1, l, r, mid, R));
}
// const int delta = 1e9;
void Solve(int rv){
vector<int> ord(n, 0);
iota(all(ord), 0);
sort(all(ord), [&](int i, int j){
// if(H[i] == H[j])
return pii(H[i], rv * i) < pii(H[j], rv * j);
});
fill(sz, sz + N, 1);
iota(par,par +N, 0);
fill(dp, dp + N, 0);
// ll delta = 1e9;
// _ln = {0, delta};
// Add_Line(1, 0, n + 1, 0, n + 1);
for(int i = 0; i < N*3; i++)
lz[i] = {0, 0}, val_l[i] = val_r[i] = 0;
for(int i = 0; i < N; i++) Q[i].clear();
for(int i = 0; i < n; i++) A[i] = pii(H[i], rv * i);
BB(1, 0, n);
////////////////////////////
for(int i = 0; i < q; i++){
pii mx = GT(1, L[i], R[i] + 1, 0, n);
int idx = mx.S / rv;
// int idx = L[i];
// for(int j = L[i]; j <= R[i]; j++)
// if(pii(H[j], rv * j) > pii(H[idx], rv * idx))
// idx = j;
// assert(idx == idx2);
Q[idx].pb(i);
}
for(int i : ord){
for(int q_id : Q[i]){
ans[q_id] = min(ans[q_id], 1ll * H[i] * (i - L[q_id] + 1) + Get(1, R[q_id] + 1, 0, n + 1));
}
Merge(i, i + 1, H[i]);
// cerr << "# " << i << '\n';
// cerr << "!! ";
// for(int i = 0; i <= n; i++)
// cerr << Get(1, i, 0, n + 1) << ' ';
// cerr << '\n';
}
}
vector<long long> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R) {
H = _H; L = _L; R = _R;
n = H.size();
q = L.size();
// Build(1, 0, n + 1);
fill(ans, ans + N, Inf);
Solve(+1);
reverse(all(H));
for(auto &x : L) x = n - 1 - x;
for(auto &x : R) x = n - 1 - x;
L.swap(R);
Solve(-1);
vector<long long> ANS;
for(int i = 0; i < q; i++)
ANS.pb(ans[i]);
return ANS;
}
