#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Inf = 1e18;
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
int q = l.size();
int n = h.size();
vector<ll> ans(q, Inf);
vector<ll> pre(n), suf(n);
for (int i = 0; i < q; i++) {
{
ll sum = 0;
deque<pair<ll, ll>> q;
for (int j = l[i]; j <= r[i]; j++) {
ll cnt = 1;
while (!q.empty() && q.front().first <= h[j]) {
cnt += q.front().second;
sum -= q.front().first * q.front().second;
q.pop_front();
}
sum += cnt * h[j];
q.push_front({h[j], cnt});
pre[j] = sum;
}
}
{
ll sum = 0;
deque<pair<ll, ll>> q;
for (int j = r[i]; j >= l[i]; j--) {
ll cnt = 1;
while (!q.empty() && q.front().first <= h[j]) {
cnt += q.front().second;
sum -= q.front().first * q.front().second;
q.pop_front();
}
sum += cnt * h[j];
q.push_front({h[j], cnt});
suf[j] = sum;
}
}
for (int j = l[i]; j <= r[i]; j++) {
ans[i] = min(ans[i], pre[j] + suf[j] - h[j]);
}
}
return ans;
}
