#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
std::vector<int> minimum_costs(std::vector<int32_t> H, std::vector<int32_t> l,
std::vector<int32_t> r) {
int n = H.size();
vector<int> h(n+1);
for (int i = 1; i <= n; i++) h[i] = H[i-1];
int q = l.size();
vector<int> o;
for (int i = 0; i < q; i++) {
vector<int> pre(n+1, 0);
stack<array<int, 3>> st;
l[i]++, r[i]++;
for (int j = l[i]; j <= r[i]; j++) {
int lm = j;
pre[j] = pre[j - 1];
while (!st.empty() && h[j] >= st.top()[2]) {
pre[j] -= (st.top()[1] - st.top()[0] + 1) * (st.top()[2]);
lm = st.top()[0], st.pop();
}
pre[j] += (j - lm + 1) * h[j];
st.push({lm, j, h[j]});
}
vector<int> suf(n+2, 0);
while (!st.empty()) st.pop();
for (int j = r[i]; j >= l[i]; j--) {
int lm = j;
suf[j] = suf[j + 1];
while (!st.empty() && h[j] >= st.top()[2]) {
suf[j] -= (st.top()[1] - st.top()[0] + 1) * (st.top()[2]);
lm = st.top()[1], st.pop();
}
suf[j] += (lm - j + 1) * h[j];
st.push({j, lm, h[j]});
}
int ans = 1e18;
for (int j = l[i]; j <= r[i]; j++) {
// cout << l[i] << " " << r[i] << " " << j << " " << pre[j] << " " << suf[j] << " " << pre[j] + suf[j] << '\n';
ans = min(ans, pre[j] + suf[j] - h[j]);
}
o.push_back(ans);
}
return o;
}
