#include "meetings.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define ALL(x) begin(x), end(x)
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
int n = H.size();
int Q = L.size();
std::vector<long long> C(Q);
for (int i = 0; i < Q; i++) {
int l = L[i], r = R[i];
stack<ii> stk;
vll suf(r+2, 0);
for (int j = r; j >= l; j--) {
while (stk.size() && H[j] >= stk.top().first) stk.pop();
ll res = 0;
if (stk.empty()) {
res = 1LL*(r-j+1)*H[j];
stk.push({H[j], j});
} else {
res = suf[stk.top().second] + 1LL*(stk.top().second-j)*H[j];
stk.push({H[j], j});
}
suf[j] = res;
}
while (stk.size()) stk.pop(); // clear
vll pre(r+1);
for (int j = l; j <= r; j++) {
while (stk.size() && H[j] >= stk.top().first) stk.pop();
ll res = 0;
if (stk.empty()) {
res = 1LL*(j-l+1)*H[j];
stk.push({H[j], j});
} else {
res = pre[stk.top().second] + 1LL*(j-stk.top().second)*H[j];
stk.push({H[j], j});
}
pre[j] = res;
}
ll best = 1e18;
for (int j = l; j <= r; j++) {
best = min(best, pre[j] + suf[j+1]);
}
C[i] = best;
}
return C;
}
/*
4 2
2 4 3 5
0 2
1 3
*/
