#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 750750;
const int NODES = 8 * MAX;
const int LOG = 20;
const long long inf = (long long) 1e18;
int n, q, a[MAX], ql[MAX], qr[MAX];
int logs[MAX], idx[MAX][LOG];
vector<int> qs[MAX];
vector<long long> res;
struct Line {
long long k;
long long n;
Line(long long _k = 0, long long _n = inf) : k(_k), n(_n) {}
long long val(long long x) {
return k * x + n;
}
} seg[2][NODES];
long long tag[2][NODES];
int cmp(int i, int j) { return a[i] > a[j] ? i : j; }
int getMax(int l, int r) {
int k = logs[r - l + 1];
return cmp(idx[l][k], idx[r - (1 << k) + 1][k]);
}
void push(int t, int id) {
seg[t][id * 2].n += tag[t][id];
seg[t][id * 2 + 1].n += tag[t][id];
tag[t][id * 2] += tag[t][id];
tag[t][id * 2 + 1] += tag[t][id];
tag[t][id] = 0;
}
void build(int id, int l, int r) {
if (l == r) {
seg[0][id] = Line(0, 0);
seg[1][id] = Line(0, 0);
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
}
long long query(int t, int id, int l, int r, int p) {
push(t, id);
if (l == r) {
return seg[t][id].val(p);
}
int mid = (l + r) >> 1;
if (p <= mid) {
return min(seg[t][id].val(p), query(t, id * 2, l, mid, p));
} else {
return min(seg[t][id].val(p), query(t, id * 2 + 1, mid + 1, r, p));
}
}
void increase(int t, int id, int l, int r, int ll, int rr, long long v) {
if (ll <= l && r <= rr) {
seg[t][id].n += v;
tag[t][id] += v;
push(t, id);
return;
}
push(t, id);
int mid = (l + r) >> 1;
if (rr <= mid) {
increase(t, id * 2, l, mid, ll, rr, v);
} else if (ll > mid) {
increase(t, id * 2 + 1, mid + 1, r, ll, rr, v);
} else {
increase(t, id * 2, l, mid, ll, rr, v);
increase(t, id * 2 + 1, mid + 1, r, ll, rr, v);
}
}
void modify(int t, int id, int l, int r, int ll, int rr, Line ln) {
if (l > r || l > rr || r < ll) {
return;
}
push(t, id);
int mid = (l + r) >> 1;
if (ll <= l && r <= rr) {
if (ln.val(mid) < seg[t][id].val(mid)) {
swap(ln, seg[t][id]);
}
if (ln.val(l) < seg[t][id].val(l)) {
modify(t, id * 2, l, mid, ll, rr, ln);
} else {
modify(t, id * 2 + 1, mid + 1, r, ll, rr, ln);
}
return;
}
modify(t, id * 2, l, mid, ll, rr, ln);
modify(t, id * 2 + 1, mid + 1, r, ll, rr, ln);
}
void solve(int l, int r) {
if (l > r) {
return;
}
int mid = getMax(l, r);
solve(l, mid - 1);
solve(mid + 1, r);
for (int i : qs[mid]) {
res[i] = min(query(0, 1, 0, n - 1, qr[i]) + (mid - ql[i] + 1) * 1LL * a[mid],
query(1, 1, 0, n - 1, ql[i]) + (qr[i] - mid + 1) * 1LL * a[mid]);
}
increase(0, 1, 0, n - 1, mid, r, a[mid] * 1LL * (r - mid + 1));
increase(1, 1, 0, n - 1, l, mid, a[mid] * 1LL * (mid - l + 1));
if (l != mid) {
modify(0, 1, 0, n - 1, mid, r, Line(a[mid], query(0, 1, 0, n - 1, mid - 1) - (mid - 1) * 1LL * a[mid]));
}
if (r != mid) {
modify(1, 1, 0, n - 1, l, mid, Line(-a[mid], query(1, 1, 0, n - 1, mid + 1) + (mid + 1) * 1LL * a[mid]));
}
}
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
n = (int) h.size();
q = (int) l.size();
for (int i = 0; i < n; i++) {
a[i] = h[i];
}
for (int i = 0; i < q; i++) {
ql[i] = l[i];
qr[i] = r[i];
}
for (int i = 2; i <= n; i++) {
logs[i] = logs[i >> 1] + 1;
}
for (int i = 0; i < n; i++) {
idx[i][0] = i;
}
for (int j = 1; j < LOG; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
idx[i][j] = cmp(idx[i][j - 1], idx[i + (1 << (j - 1))][j - 1]);
}
}
build(1, 0, n - 1);
res.resize(q);
for (int i = 0; i < q; i++) {
qs[getMax(l[i], r[i])].push_back(i);
}
solve(0, n - 1);
return res;
}
