#include <bits/stdc++.h>
using namespace std;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
const int n = H.size();
const int q = R.size();
vector<long long> ans(q);
vector<vector<int>> queries(n);
vector<int> qidx(q);
for (int i = 0; i < q; ++i) qidx[i] = i;
sort(qidx.begin(), qidx.end(), [&] (int a, int b) {
return R[a] < R[b];
});
const int NULL_NODE = -1;
vector<pair<int, int>> child(n, {NULL_NODE, NULL_NODE});
int root = NULL_NODE;
{
vector<int> stk;
int qiter = 0;
for (int u = 0; u < n; ++u) {
while (!stk.empty() && H[stk.back()] <= H[u]) {
const int v = stk.back();
stk.pop_back();
child[u].first = v;
}
if (!stk.empty()) {
child[stk.back()].second = u;
} else {
root = u;
}
stk.push_back(u);
while (qiter < q && R[qidx[qiter]] == u) {
const int i = qidx[qiter++];
const int v = *lower_bound(stk.begin(), stk.end(), L[i]);
queries[v].push_back(i);
}
}
assert(qiter == q);
assert(root != NULL_NODE);
}
using line = tuple<int, int, long long>;
struct best_fn {
int len;
int idx_offset;
long long val_offset;
set<line> lines;
long long query(int idx) const {
if (idx == -1) return 0LL;
assert(0 <= idx && idx < len);
idx -= idx_offset;
auto it = lines.lower_bound({idx+1, 0, -val_offset});
assert(it != lines.begin());
const auto& [pos, slope, value] = *prev(it);
const long long ans = val_offset + value + (long long) slope * (idx - pos);
return ans;
}
void add_line(int idx, int slope, long long val) {
assert(0 <= idx && idx < len);
const line new_line = { idx - idx_offset, slope, val - val_offset};
lines.insert(new_line);
}
};
const auto merge = [&] (best_fn& l1, long long h, best_fn& l2) {
const long long ans = l1.query(l1.len-1);
const long long first_val = ans + h;
const int first_slope = h;
l2.idx_offset += 1;
l2.val_offset += (long long) h * (l1.len + 1);
l2.len += 1;
while (!l2.lines.empty()) {
const auto fs = l2.lines.begin();
auto [pos, slope, val] = *fs;
pos += l2.idx_offset;
val += l2.val_offset;
if (first_val + (long long) pos * first_slope > val) {
break;
} else {
l2.lines.erase(fs);
const auto it = l2.lines.begin();
const int next_pos = (it != l2.lines.end() ? get<0>(*it) + l2.idx_offset : l2.len) - 1;
if (first_val + (long long) next_pos * first_slope > val + (long long) (next_pos - pos) * slope) {
const int new_pos = (val - first_val - (long long) pos * slope) / (first_slope - slope) + 1;
assert(pos < new_pos && new_pos <= next_pos);
const long long new_val = val + (long long) (new_pos - pos) * slope;
l2.add_line(new_pos, slope, new_val);
break;
}
}
}
l2.add_line(0, first_slope, first_val);
l2.idx_offset += l1.len;
if (l1.lines.size() < l2.lines.size()) {
swap(l1, l2);
}
l1.len += l2.len;
for (const auto& [pos, slope, val] : l2.lines) {
l1.add_line(pos + l2.idx_offset, slope, val + l2.val_offset);
}
};
using build_result = pair<best_fn*, best_fn*>;
const auto empty_best_result = [&] () -> build_result {
auto fn1 = new best_fn {0, 0, 0LL, {}};
auto fn2 = new best_fn {0, 0, 0LL, {}};
return {fn1, fn2};
};
vector<build_result> tree(n);
const function<void(int u)> calc_best = [&] (const int u) {
if (u == NULL_NODE) return;
const auto [v1, v2] = child[u];
calc_best(v1);
calc_best(v2);
auto [l_v1, r_v1] = (v1 != NULL_NODE ? tree[v1] : empty_best_result());
auto [l_v2, r_v2] = (v2 != NULL_NODE ? tree[v2] : empty_best_result());
for (const int qid : queries[u]) {
const int l = L[qid], r = R[qid];
assert(l <= u && u <= r);
const long long ans_u = (long long) H[u] * (r - l + 1);
const int r_v1_idx = (u-1) - l;
const long long ans_l = r_v1->query(r_v1_idx) + (long long) H[u] * (r - u + 1);
const int l_v2_idx = r - (u+1);
const long long ans_r = l_v2->query(l_v2_idx) + (long long) H[u] * (u - l + 1);
ans[qid] = min(ans_u, min(ans_l, ans_r));
}
merge(*l_v1, H[u], *l_v2);
merge(*r_v2, H[u], *r_v1);
tree[u] = {l_v1, r_v2};
};
calc_best(root);
return ans;
}
