#include <bits/stdc++.h>
using namespace std;
#include "meetings.h"
const int N = 750000, L = __lg(N) + 1;
struct range {
long long mini, sum;
int size, par;
} nxt_l[L][N], nxt_r[L][N];
vector<int> h;
range combine(range l, range r) {
if (r.par == -1) {
return {0, 0, 0, -1};
} else {
return {
min(l.mini + r.sum, (long long) h[l.par] * l.size + r.mini),
l.sum + r.sum,
l.size + r.size,
r.par
};
}
}
void calc(int k, int i) {
if (nxt_r[k][i].par != -1 || k == 0) {
return;
}
calc(k - 1, i);
int p = nxt_r[k - 1][i].par;
if (p != -1) {
calc(k - 1, p);
nxt_r[k][i] = combine(nxt_r[k - 1][i], nxt_r[k - 1][p]);
}
}
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
int n = h.size(), q = l.size();
::h = h;
for (int i = 0; i <= __lg(n); ++i) {
for (int j = 0; j < n; ++j) {
nxt_l[i][j].par = nxt_r[i][j].par = -1;
}
}
vector<int> stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && h[stk.back()] <= h[i]) {
int j = stk.back();
stk.pop_back();
range mini = {0, 0, 0, i - 1};
for (int k = __lg(n); k >= 0; --k) {
int p = nxt_l[k][mini.par].par;
if (p >= j) {
mini = combine(mini, nxt_l[k][mini.par]);
}
}
nxt_r[0][j] = {
mini.mini + h[j],
(long long) h[j] * (i - j),
i - j, i
};
}
if (!stk.empty()) {
int j = stk.back();
range mini = {0, 0, 0, j + 1};
for (int k = __lg(n); k >= 0; --k) {
calc(k, mini.par);
int p = nxt_r[k][mini.par].par;
if (p != -1 && p <= i) {
mini = combine(mini, nxt_r[k][mini.par]);
}
}
nxt_l[0][i] = {
mini.mini + h[i],
(long long) h[i] * (i - j),
i - j, j
};
for (int k = 1; k <= __lg(n); ++k) {
int p = nxt_l[k - 1][i].par;
if (p != -1) {
nxt_l[k][i] = combine(nxt_l[k - 1][i], nxt_l[k - 1][p]);
}
}
}
stk.push_back(i);
}
vector<long long> c(q);
for (int i = 0; i < q; ++i) {
range left = {0, 0, 0, l[i]};
for (int k = __lg(n); k >= 0; --k) {
calc(k, left.par);
int p = nxt_r[k][left.par].par;
if (p != -1 && p <= r[i]) {
left = combine(left, nxt_r[k][left.par]);
}
}
range right = {0, 0, 0, r[i]};
for (int k = __lg(n); k >= 0; --k) {
int p = nxt_l[k][right.par].par;
if (p >= l[i]) {
right = combine(right, nxt_l[k][right.par]);
}
}
int maxi = left.par;
c[i] = min(
left.mini + (long long) (r[i] - maxi + 1) * h[maxi],
right.mini + (long long) (maxi - l[i] + 1) * h[maxi]
);
}
return c;
}
