#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
vll minimum_costs (vi H, vi l, vi r) {
vll ve(H.begin(), H.end());
ll n = ve.size();
ll Q = l.size();
vll ans(Q, -15);
for (ll q = 0; q < Q; q++) {
vll lh(n), rh(n);
{vll stkVal;
vll stkSz;
stkVal.push_back(1E18);
stkSz.push_back(0);
ll cans = 0;
for (ll i = l[q]; i <= r[q]; i++) {
ll sz = 1;
while (ve[i] > stkVal.back()) {
cans -= stkVal.back() * stkSz.back();
sz += stkSz.back();
stkVal.pop_back();
stkSz.pop_back();
}
stkVal.push_back(ve[i]);
stkSz.push_back(sz);
cans += ve[i]*sz;
lh[i] = cans;
}}
{vll stkVal;
vll stkSz;
stkVal.push_back(1E18);
stkSz.push_back(0);
ll cans = 0;
for (ll i = r[q]; i >= l[q]; i--) {
ll sz = 1;
while (ve[i] > stkVal.back()) {
cans -= stkVal.back() * stkSz.back();
sz += stkSz.back();
stkVal.pop_back();
stkSz.pop_back();
}
stkVal.push_back(ve[i]);
stkSz.push_back(sz);
cans += ve[i]*sz;
rh[i] = cans;
}}
ll qans = 1E18;
for (ll i = l[q]; i <= r[q]; i++) {
qans = min(qans, lh[i]+rh[i]-ve[i]);
}
ans[q] = qans;
}
return ans;
}
