#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "meetings.h"
const int XN = 1e6;
const int INF = 0x3f3f3f3f;
int s[XN], v[XN], p;
ll sum;
ll pref[XN], suff[XN];
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
int q = (int)l.size();
vector<ll> c(q);
for (int it = 0; it < q; ++it) {
sum = 0;
p = 0;
v[p] = INF;
s[p++] = l[it] - 1;
for (int i = l[it]; i <= r[it]; ++i) {
while (v[p - 1] < h[i]) {
--p;
assert(p);
sum -= (ll)v[p] * (s[p] - s[p - 1]);
}
v[p] = h[i];
s[p] = i;
sum += (ll)v[p] * (s[p] - s[p - 1]);
++p;
pref[i] = sum;
}
sum = 0;
p = 0;
v[p] = INF;
s[p++] = r[it] + 1;
for (int i = r[it]; i >= l[it]; --i) {
while (v[p - 1] < h[i]) {
--p;
assert(p);
sum -= (ll)v[p] * (s[p - 1] - s[p]);
}
v[p] = h[i];
s[p] = i;
sum += (ll)v[p] * (s[p - 1] - s[p]);
++p;
suff[i] = sum - h[i];
}
c[it] = pref[l[it]] + suff[l[it]];
for (int i = l[it]; i <= r[it]; ++i) {
// cout << pref[i] + suff[i] << endl;
c[it] = min(c[it], pref[i] + suff[i]);
}
}
return c;
}
#ifdef LC
#include "grader.cpp"
#endif
