#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const ll INF = 1LL << 60;
vi minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R)
{
int N = sz(H);
int Q = L.size();
vi ans(Q);
vi dpL(N), dpR(N);
for (int j = 0; j < Q; ++j)
{
ll tmp = 0;
stack<pii> st; // { value, number}
st.push({INF, 0});
for (int i = L[j]; i <= R[j]; ++i)
{
ll num = 1;
while (st.top().first <= H[i])
{
tmp -= st.top().first * st.top().second;
num += st.top().second;
st.pop();
}
st.push({H[i], num});
tmp += H[i] * num;
dpL[i] = tmp;
}
tmp = 0;
while (!st.empty())
st.pop();
st.push({INF, 0});
for (int i = R[j]; i >= L[j]; --i)
{
ll num = 1;
while (st.top().first <= H[i])
{
tmp -= st.top().first * st.top().second;
num += st.top().second;
st.pop();
}
st.push({H[i], num});
tmp += H[i] * num;
dpR[i] = tmp;
}
ans[j] = INF;
for (int i = L[j]; i <= R[j]; ++i)
ans[j] = min(ans[j], dpL[i] + dpR[i] - H[i]);
}
return ans;
}
