#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[N], nxt_r[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
};
}
}
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 < n; ++i) {
nxt_l[i].par = nxt_r[i].par = -1;
}
vector<int> less, greater;
for (int i = 0; i < n; ++i) {
while (!less.empty() && h[less.back()] < h[i]) {
int j = less.back();
less.pop_back();
range mini = {0, 0, 0, i - 1};
while (true) {
range temp = combine(mini, nxt_l[mini.par]);
if (temp.par < j) {
break;
}
mini = temp;
}
nxt_r[j] = {
mini.mini + h[j],
(long long) h[j] * (i - j),
i - j, i
};
}
while (!greater.empty() && h[greater.back()] <= h[i]) {
greater.pop_back();
}
if (!greater.empty()) {
int j = greater.back();
range mini = {0, 0, 0, j + 1};
while (true) {
range temp = combine(mini, nxt_r[mini.par]);
if (temp.par == -1 || temp.par > i) {
break;
}
mini = temp;
}
nxt_l[i] = {
mini.mini + h[i],
(long long) h[i] * (i - j),
i - j, j
};
}
greater.push_back(i);
less.push_back(i);
}
vector<long long> c(q);
for (int i = 0; i < q; ++i) {
range left = {0, 0, 0, l[i]};
while (true) {
range temp = combine(left, nxt_r[left.par]);
if (temp.par == -1 || temp.par > r[i]) {
break;
}
left = temp;
}
range right = {0, 0, 0, r[i]};
while (true) {
range temp = combine(right, nxt_l[right.par]);
if (temp.par < l[i]) {
break;
}
right = temp;
}
c[i] = min(
left.mini + (long long) (r[i] - left.par + 1) * h[left.par],
right.mini + (long long) (right.par - l[i] + 1) * h[right.par]
);
}
return c;
}
