#include <bits/stdc++.h>
using namespace std;
#include "meetings.h"
const int N = 750000, L = __lg(N) + 1;
long long mini_l[L][N], mini_r[L][N], sum_l[L][N], sum_r[L][N];
int par_l[L][N], par_r[L][N];
vector<int> h;
void calc(int i, int l) {
if (par_r[i][l] != -1 || i == 0) {
return;
}
calc(i - 1, l);
int p = par_r[i - 1][l];
if (p == -1) {
return;
}
calc(i - 1, p);
par_r[i][l] = par_r[i - 1][p];
sum_r[i][l] = sum_r[i - 1][l] + sum_r[i - 1][p];
mini_r[i][l] = min(
(long long) h[p] * (p - l) + mini_r[i - 1][p],
mini_r[i - 1][l] + sum_r[i - 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) {
par_l[i][j] = par_r[i][j] = -1;
sum_l[i][j] = sum_r[i][j] = 0;
mini_l[i][j] = mini_r[i][j] = 0;
}
}
vector<int> stk;
for (int r = 0; r < n; ++r) {
while (!stk.empty() && h[stk.back()] <= h[r]) {
int l = stk.back();
stk.pop_back();
int u = r - 1;
long long mini = 0;
for (int i = __lg(n); i >= 0; --i) {
if (par_l[i][u] >= l) {
mini = min(
(long long) h[u] * (r - 1 - u) + mini_l[i][u],
mini + sum_l[i][u]
);
u = par_l[i][u];
}
}
mini += h[l];
par_r[0][l] = r;
mini_r[0][l] = mini;
sum_r[0][l] = (long long) h[l] * (r - l);
}
if (!stk.empty()) {
int l = stk.back();
int u = l + 1;
long long mini = 0;
for (int i = __lg(n); i >= 0; --i) {
calc(i, u);
if (par_r[i][u] != -1) {
mini = min(
(long long) h[u] * (u - l - 1) + mini_r[i][u],
mini + sum_r[i][u]
);
u = par_r[i][u];
}
}
mini += h[r];
par_l[0][r] = l;
mini_l[0][r] = mini;
sum_l[0][r] = (long long) h[r] * (r - l);
for (int i = 1; i <= __lg(n); ++i) {
int p = par_l[i - 1][r];
if (p != -1) {
par_l[i][r] = par_l[i - 1][p];
sum_l[i][r] = sum_l[i - 1][r] + sum_l[i - 1][p];
mini_l[i][r] = min(
(long long) h[p] * (r - p) + mini_l[i - 1][p],
mini_l[i - 1][r] + sum_l[i - 1][p]
);
}
}
}
stk.push_back(r);
}
vector<long long> c(q);
for (int i = 0; i < q; ++i) {
int u = l[i];
long long left = 0;
for (int j = __lg(n); j >= 0; --j) {
calc(j, u);
int p = par_r[j][u];
if (p != -1 && p <= r[i]) {
left = min(
(long long) h[u] * (u - l[i]) + mini_r[j][u],
left + sum_r[j][u]
);
u = p;
}
}
left += (long long) (r[i] - u + 1) * h[u];
u = r[i];
long long right = 0;
for (int j = __lg(n); j >= 0; --j) {
int p = par_l[j][u];
if (p >= l[i]) {
right = min(
(long long) h[u] * (r[i] - u) + mini_l[j][u],
right + sum_l[j][u]
);
u = p;
}
}
right += (long long) (u - l[i] + 1) * h[u];
c[i] = min(left, right);
}
return c;
}
