#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> h, ql, qr;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
h = H; ql = L, qr = R;
int n = (int) H.size();
int q = (int) L.size();
vector<long long> ret(q, LLONG_MAX);
for (int qind = 0; qind < q; ++qind) {
stack<pair<int, int>> stk; //element, occurrence
long long res = 0;
vector<long long> ans(n);
for (int i = ql[qind]; i <= qr[qind]; ++i) {
int f = 1;
while (!stk.empty() && stk.top().first < h[i]) {
auto [element, cnt] = stk.top();
stk.pop();
f += cnt;
res -= (long long) element * cnt;
}
stk.push({h[i], f});
res += (long long) h[i] * f;
ans[i] = res;
}
while (!stk.empty()) {
stk.pop();
}
res = 0;
for (int i = qr[qind]; i >= ql[qind]; --i) {
int f = 1;
while (!stk.empty() && stk.top().first < h[i]) {
auto [element, cnt] = stk.top();
stk.pop();
f += cnt;
res -= (long long) element * cnt;
}
stk.push({h[i], f});
res += (long long) h[i] * f;
ans[i] += res - h[i];
ret[qind] = min(ret[qind], ans[i]);
}
}
return ret;
}
