#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll const inf = 0x3f3f3f3f3f3f3f3f;
vector<ll> minimum_costs(vector<int> h, vector<int> L,
vector<int> R) {
int n = h.size();
vector<int> a(n), b(n);
stack<int> pre;
for (int i = 0; i < n; i++) {
while (!pre.empty() and h[pre.top()] < h[i]) {
b[pre.top()] = i;
pre.pop();
}
pre.push(i);
}
while (!pre.empty()) {
b[pre.top()] = n;
pre.pop();
}
reverse(h.begin(), h.end());
for (int i = 0; i < n; i++) {
while (!pre.empty() and h[pre.top()] < h[i]) {
a[pre.top()] = i;
pre.pop();
}
pre.push(i);
}
while (!pre.empty()) {
a[pre.top()] = n;
pre.pop();
}
reverse(h.begin(), h.end());
for (int& i : a) i = n-1-i;
reverse(a.begin(), a.end());
int q = L.size();
vector<ll> res;
for (int at = 0; at < q; at++) {
ll ans = inf;
int l = L[at], r = R[at];
vector<ll> resl(r-l+1);
vector<ll> resr(r-l+1);
for (int i = l; i <= r; i++) {
if (a[i] < l) resl[i-l] = ll(h[i])*(i-l+1);
else resl[i-l] = resl[a[i]-l] + (i-a[i])*h[i];
}
for (int i = r; i >= l; i--) {
if (b[i] > r) resr[i-l] = ll(h[i])*(r-i+1);
else resr[i-l] = resr[b[i]-l] + (b[i]-i)*h[i];
}
for (int i = l; i <= r; i++) {
ans = min(ans, resl[i-l] + resr[i-l] - h[i]);
}
res.push_back(ans);
}
return res;
}
