#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
namespace debug {
const int DEBUG = false;
template<class T1, class T2>
void pr(const pair<T1, T2> &x);
template<class T, size_t SZ>
void pr(const array<T, SZ> &x);
template<class T>
void pr(const vector<T> &x);
template<class T>
void pr(const set<T> &x);
template<class T1, class T2>
void pr(const map<T1, T2> &x);
template<class T>
void pr(const T &x) { if (DEBUG) cout << x; }
template<class T, class... Ts>
void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }
template<class T1, class T2>
void pr(const pair<T1, T2> &x) { pr("{", x.y, ", ", x.s, "}"); }
template<class T>
void prIn(const T &x) {
pr("{");
bool fst = 1;
for (auto &a : x) {
pr(fst ? "" : ", ", a), fst = 0;
}
pr("}");
}
template<class T, size_t SZ>
void pr(const array<T, SZ> &x) { prIn(x); }
template<class T>
void pr(const vector<T> &x) { prIn(x); }
template<class T>
void pr(const set<T> &x) { prIn(x); }
template<class T1, class T2>
void pr(const map<T1, T2> &x) { prIn(x); }
void ps() { pr("\n"); }
template<class Arg, class... Args>
void ps(const Arg &first, const Args &... rest) {
pr(first, " ");
ps(rest...);
}
}
using namespace debug;
const int MAXN = 1e6 + 5;
const int LOGN = 21;
const ll INF = 1e16;
struct Line {
ll m;
ll b;
ll y(int x) {
return m * x + b;
}
Line(ll mI = 0, ll bI = INF) {
m = mI;
b = bI;
}
};
Line tr[4 * MAXN];
ll lz[4 * MAXN];
void uL(int i, int l, int r, int s, int e, Line line) {
if (e < l || r < s) {
return;
}
line.b -= lz[i];
if (s <= l && r <= e) {
if (l == r) {
if (line.y(l) < tr[i].y(l)) {
tr[i] = line;
}
} else {
int mid = (l + r) / 2;
bool bF = line.y(l) < tr[i].y(l);
bool bM = line.y(mid) < tr[i].y(mid);
if (bF) {
if (bM) {
swap(tr[i], line);
uL(i * 2 + 1, mid + 1, r, s, e, line);
} else {
uL(i * 2, l, mid, s, e, line);
}
} else {
if (bM) {
swap(tr[i], line);
uL(i * 2, l, mid, s, e, line);
} else {
uL(i * 2 + 1, mid + 1, r, s, e, line);
}
}
}
return;
}
int mid = (l + r) / 2;
uL(i * 2, l, mid, s, e, line);
uL(i * 2 + 1, mid + 1, r, s, e, line);
}
void uC(int i, int l, int r, int s, int e, ll d) {
if (e < l || r < s) {
return;
}
if (s <= l && r <= e) {
lz[i] += d;
return;
}
int mid = (l + r) / 2;
uC(i * 2, l, mid, s, e, d);
uC(i * 2 + 1, mid + 1, r, s, e, d);
}
ll q(int i, int l, int r, int x) {
if (l == r) {
return lz[i] + tr[i].y(x);
}
int mid = (l + r) / 2;
if (x <= mid) {
return lz[i] + min(tr[i].y(x), q(i * 2, l, mid, x));
} else {
return lz[i] + min(tr[i].y(x), q(i * 2 + 1, mid + 1, r, x));
}
}
int log2d(int x) {
return 31 - __builtin_clz(x);
}
pi tb[MAXN][LOGN];
void init() {
for (int k = 1; k < LOGN; k++) {
for (int i = 0; i < MAXN; i++) {
int nI = i + (1 << (k - 1));
if (nI < MAXN) {
tb[i][k] = max(tb[i][k - 1], tb[nI][k - 1]);
} else {
tb[i][k] = tb[i][k - 1];
}
}
}
}
pi qMax(int l, int r) {
int k = log2d(r - l + 1);
return max(tb[l][k], tb[r - (1 << k) + 1][k]);
}
struct Query {
int l;
int r;
int i;
};
vector<Query> queries[MAXN];
vl ans;
int N, Q;
void process(int l, int r) {
// ps("process", l, r);
pi mP = qMax(l, r);
ll mH = mP.f;
int mI = abs(mP.s);
if (l < mI) {
process(l, mI - 1);
}
if (mI < r) {
process(mI + 1, r);
}
for (Query cQ : queries[mI]) {
if (cQ.r > mI) {
ans[cQ.i] = min(ans[cQ.i], q(1, 1, MAXN, cQ.r) + (mI - cQ.l + 1ll) * mH);
}
}
uC(1, 1, MAXN, mI, r, (mI - l + 1ll) * mH);
ll lCost = l < mI ? q(1, 1, MAXN, mI - 1) : 0;
uL(1, 1, MAXN, mI, r, Line(mH, lCost - (mI - 1ll) * mH));
}
void calculate(vi &H, vi &L, vi &R, int flip = 1) {
for (int i = 0; i < 4 * MAXN; i++) {
tr[i] = Line();
lz[i] = 0;
}
for (int i = 0; i < MAXN; i++) {
queries[i].clear();
}
for (int i = 0; i < N; i++) {
tb[i][0] = {H[i], i * flip};
}
init();
for (int i = 0; i < Q; i++) {
queries[flip * qMax(L[i], R[i]).s].pb({L[i], R[i], i});
}
process(0, N - 1);
}
vl minimum_costs(vi H, vi L, vi R) {
ps("read");
N = H.size();
Q = L.size();
ans.resize(Q, INF);
calculate(H, L, R);
// reverse
for (int i = 0; i < N / 2; i++) {
swap(H[i], H[N - 1 - i]);
}
for (int i = 0; i < Q; i++) {
L[i] = N - 1 - L[i];
R[i] = N - 1 - R[i];
swap(L[i], R[i]);
}
//
calculate(H, L, R, -1);
for (int i = 0; i < Q; i++) {
ans[i] = min(ans[i], (R[i] - L[i] + 1ll) * qMax(L[i], R[i]).f);
}
return ans;
}
