#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
struct func {
int a;
ll b, c;
func() {
a = 1, b = c = 0;
}
func(int aa, ll bb, ll cc) : a(aa), b(bb), c(cc) {}
// this * x
func operator * (const func &x) const {
return func(a * x.a, a * x.b + b, a * x.c + c);
}
// x * this
void operator *= (const func &x) {
a = x.a * a;
b = x.a * b + x.b;
c = x.a * c + x.c;
}
ll operator () (ll x, int i) const {
return a * x + b * i + c;
}
};
struct segtree {
int n;
vector<ll> t;
vector<int> ind;
vector<func> tag;
segtree() {}
segtree(int sz) {
init(sz);
}
void init(int sz) {
n = max(2, sz);
while (n != (n & -n)) n += (n & -n);
t.resize(2 * n, 0);
tag.resize(2 * n, func());
ind.resize(2 * n);
for (int i = 0; i < n; i++)
ind[i + n - 1] = i;
for (int i = n - 2; i >= 0; i--)
ind[i] = ind[2 * i + 1];
}
void clear() {
for (auto &i : t) i = 0;
for (auto &i : tag) i = func();
}
void push(int x) {
t[x] = tag[x](t[x], ind[x]);
if (x < n - 1) {
tag[2 * x + 1] *= tag[x];
tag[2 * x + 2] *= tag[x];
}
tag[x] = func();
}
// assumes x has no tag
void fix(int x) {
push(2 * x + 1);
t[x] = t[2 * x + 1];
}
// a[i] = x
void set(ll x, int i) {
func f(0, 0, x);
upd(i, i, f, 0, 0, n - 1);
}
inline func progressf(int l, int r, ll st, ll d) {
return func(1, d, st - d * l);
}
// for each i in [l, r], add st + d * (i - l)
void progress(int l, int r, ll st, ll d) {
func f(1, d, st - d * l);
upd(l, r, f, 0, 0, n - 1);
}
// for each i in monotonic [l, r], set a[i] = min(a[i], x)
void minimize(int l, int r, ll x) {
int m = last(l, r, x);
if (m != -1) {
func f(0, 0, x);
upd(l, m, f, 0, 0, n - 1);
}
}
void upd(int l, int r, const func &f, int node, int nl, int nr) {
if (r < nl || nr < l) return;
if (l <= nl && nr <= r) {
tag[node] *= f;
return;
}
push(node);
int mid = (nl + nr) / 2;
upd(l, r, f, 2 * node + 1, nl, mid);
upd(l, r, f, 2 * node + 2, mid + 1, nr);
fix(node);
}
// smallest i in [l, r] s.t a[i] >= x
int last(int l, int r, ll x) {
return last(l, r, x, 0, 0, n - 1);
}
int last(int l, int r, ll x, int node, int nl, int nr) {
if (r < nl || nr < l) return -1;
push(node);
if (l <= nl && nr <= r && t[node] < x) return -1;
if (nl == nr) return nl;
int mid = (nl + nr) / 2, tmp;
tmp = last(l, r, x, 2 * node + 2, mid + 1, nr);
if (tmp != -1) return tmp;
return last(l, r, x, 2 * node + 1, nl, mid);
}
ll operator [] (int i) const {
int org = i;
i += n - 1;
ll rtn = t[i];
rtn = tag[i](rtn, org);
i = (i - 1) / 2;
while (i) {
rtn = tag[i](rtn, org);
i = (i - 1) / 2;
}
rtn = tag[0](rtn, org);
return rtn;
}
};
struct mtree {
int n;
const ll b = 1 << 30;
vector<ll> t;
mtree() {}
mtree(const vector<int> &a) {
init(a);
}
void init(const vector<int> &a) {
n = max(2, (int)a.size());
while (n != (n & -n)) n += (n & -n);
t.resize(2 * n);
for (int i = 0; i < a.size(); i++)
t[i + n - 1] = b * a[i] + i;
for (int i = n - 2; i >= 0; i--)
t[i] = max(t[2 * i + 1], t[2 * i + 2]);
}
int query(int l, int r) const {
ll mx = -1;
for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
if (!(l & 1)) mx = max(mx, t[l++]);
if (r & 1) mx = max(mx, t[r--]);
}
if (l == r) mx = max(mx, t[l]);
return mx % b;
}
ll vquery(int l, int r) const {
ll mx = -1;
for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
if (!(l & 1)) mx = max(mx, t[l++]);
if (r & 1) mx = max(mx, t[r--]);
}
if (l == r) mx = max(mx, t[l]);
return mx / b;
}
};
struct query {
int l, r, i;
query() {}
query(int ll, int rr, int ii) : l(ll), r(rr), i(ii) {}
};
const int mxn = 750005;
int n;
vector<int> a;
int S[mxn], E[mxn], L[mxn], R[mxn], root;
vector<query> Q[mxn];
vector<ll> ans;
mtree M;
segtree T;
int preprocess(int l, int r) {
if (l > r) return -1;
int v = M.query(l, r);
if (OO) {
cout << "preprocessing in [" << l << ", " << r << "], v = " << v << '\n';
}
S[v] = l;
E[v] = r;
L[v] = preprocess(l, v - 1);
R[v] = preprocess(v + 1, r);
return v;
}
void preprocess(const vector<int> &l, const vector<int> &r) {
M.init(a);
T.init(n);
root = preprocess(0, n - 1);
for (int i = 0; i < ans.size(); i++) {
ans[i] = ll(r[i] - l[i] + 1) * M.vquery(l[i], r[i]);
int v = M.query(l[i], r[i]);
if (OO) {
cout << "attaching query " << l[i] << " " << r[i] << " to " << v << '\n';
}
Q[v].push_back(query(l[i], r[i], i));
}
}
void solve(int v, int prev) {
if (v < 0 || n <= v) return;
solve(L[v], v);
solve(R[v], v);
if (OO) cout << "solving " << v << " " << prev << '\n';
if (OO) {
cout << "before:\n";
for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
}
if (S[v] == v) T.set(a[v], v);
else T.set(T[v - 1] + a[v], v);
if (v < E[v]) {
ll c = (v > 0 ? T[v - 1] : 0) + (ll)a[v] * (1 - (v - S[v]));
/*
T.progress(v + 1, E[v], ll(a[v]) * (v - S[v] + 1), 0);
T.progress(v + 1, E[v], -ll(a[v]) * (v - S[v] + 1), -a[v]);
*/
func tmp = T.progressf(v + 1, E[v], ll(a[v]) * (v - S[v] + 1), 0);
tmp *= T.progressf(v + 1, E[v], -ll(a[v]) * (v - S[v] + 1), -a[v]);
T.upd(v + 1, E[v], tmp, 0, 0, T.n - 1);
T.minimize(v + 1, E[v], c);
T.progress(v + 1, E[v], ll(v - S[v] + 1) * a[v], a[v]);
}
if (OO) {
cout << "after:\n";
for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
}
if (prev != -1 && prev < v) {
for (const auto &i : Q[prev]) {
if (prev < i.r) {
if (OO) cout << "updating query " << i.l << " " << i.r << '\n';
ans[i.i] = min(ans[i.i], ll(prev - i.l + 1) * a[prev] + T[i.r]);
}
}
}
}
ll cost(int l, int r, int i) {
ll rtn = a[i], mx;
mx = a[i];
for (int x = i + 1; x <= r; x++) {
mx = max(mx, (ll)a[x]);
rtn += mx;
}
mx = a[i];
for (int x = i - 1; x >= l; x--) {
mx = max(mx, (ll)a[x]);
rtn += mx;
}
return rtn;
}
ll bruteforce(int l, int r) {
ll ans = inf;
for (int i = l; i <= r; i++)
ans = min(ans, cost(l, r, i));
return ans;
}
vector<ll> minimum_costs(vector<int> H, vector<int> l,
vector<int> r) {
n = H.size();
a = H;
ans.resize(l.size());
preprocess(l, r);
if (OO) {
cout << "preprocessed\n";
cout << "L: ";
for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
cout << "R: ";
for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
cout << "S: ";
for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
cout << "E: ";
for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
}
solve(root, -1);
// reverse
reverse(a.begin(), a.end());
auto flip = [](int &x, int y) {
x = y - 1 - x;
};
for (int i = 0; i < n; i++) {
flip(S[i], n);
flip(E[i], n);
swap(S[i], E[i]);
flip(L[i], n);
flip(R[i], n);
swap(L[i], R[i]);
}
for (int i = 0; i < n; i++) {
for (auto &j : Q[i]) {
flip(j.l, n);
flip(j.r, n);
swap(j.l, j.r);
}
}
reverse(Q, Q + n);
reverse(S, S + n);
reverse(E, E + n);
reverse(L, L + n);
reverse(R, R + n);
M.init(a);
T.clear();
flip(root, n);
if (OO) {
cout << "reversed\n";
cout << "L: ";
for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
cout << "R: ";
for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
cout << "S: ";
for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
cout << "E: ";
for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
cout << '\n';
cout << "current answers: ";
for (const auto &i : ans) cout << i << " "; cout << '\n';
}
solve(root, -1);
return ans;
}
