#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = L.size();
int n = H.size();
vector<ll> C(Q);
vector<int> queries(Q); iota(queries.begin(), queries.end(), 0);
sort(queries.begin(), queries.end(), [&](int a, int b) {return R[a] < R[b];});
vector<vector<ll>> left_stacks(n), right_stacks(n);
vector<ll> stL(n, 0), stR(n, 0);
int cur_query = 0;
for (int i = 0; i < n; i++) {
int cur_idx = i - 1;
while (cur_idx >= 0 && stL[cur_idx] < H[i]) {
stL[cur_idx] = H[i];
cur_idx--;
}
stL[i] = H[i];
left_stacks[i] = stL;
}
for (int i = n-1; i >= 0; i--) {
int cur_idx = i+1;
while (cur_idx < n && stR[cur_idx] < H[i]) {
stR[cur_idx] = H[i];
cur_idx++;
}
stR[i] = H[i];
right_stacks[i] = stR;
}
for (int st = 0; st < n; st++) {
for (int i = 1; i < n; i++) {
left_stacks[st][i] += left_stacks[st][i-1];
}
for (int i = n - 2; i >= 0; i--) {
right_stacks[st][i] += right_stacks[st][i+1];
}
}
auto f = [&](int i, int j) {
ll lv = left_stacks[i][i], rv = right_stacks[i][i+1];
ll lsub = L[j] == 0 ? 0 : left_stacks[i][L[j] - 1], rsub = R[j] == n - 1 ? 0 : right_stacks[i][R[j] + 1];
lv -= lsub; rv -= rsub;
return lv + rv;
};
for (int j = 0; j < Q; ++j) {
C[j] = INF;
for (int dr = 0; dr <= 1; dr++) {
C[j] = min({C[j], f(clamp(L[j] + dr, 0, n-1), j), f(clamp(R[j] - dr, 0, n-1), j)});
}
// for (int i = L[j]; i <= R[j]; i++) {
// C[j] = min(C[j], f(i, j));
// }
}
return C;
}
