#include "bits/stdc++.h"
#include "meetings.h"
using namespace std;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
int q = L.size();
int n = H.size();
vector<long long> ans(q, 1e18);
for (int i = 0; i < q; i++)
{
vector<long long> sum(n);
stack<int> st;
long long cur = 0;
for (int l = L[i]; l <= R[i]; l++)
{
while (!st.empty() && H[st.top()] <= H[l])
{
int j = st.top();
st.pop();
if (!st.empty())
cur -= 1ll * (j - st.top()) * H[j];
}
if (st.empty())
cur = 0;
cur += 1ll * (l - (st.empty() ? L[i] - 1 : st.top())) * H[l];
sum[l] += cur;
st.push(l);
}
while (!st.empty())
st.pop();
cur = 0;
for (int l = R[i]; l >= L[i]; l--)
{
while (!st.empty() && H[st.top()] <= H[l])
{
int j = st.top();
st.pop();
if (!st.empty())
cur -= 1ll * abs(j - st.top()) * H[j];
}
if (st.empty())
cur = 0;
cur += 1ll * abs(l - (st.empty() ? R[i] + 1 : st.top())) * H[l];
sum[l] += cur - H[l];
st.push(l);
}
ans[i] = *min_element(sum.begin() + L[i], sum.begin() + R[i] + 1);
}
return ans;
}
