#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e18 + 10;
constexpr int kMod = 1e9 + 7;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
const int n = H.size(), q = L.size();
vector<int64> ans(q, kInf64);
vector<int64> cost(n);
auto initialise_cost = [&]() {
for (int i = 0; i < n; i++) {
cost[i] = -H[i];
}
};
for (int query = 0; query < q; query++) {
initialise_cost();
vector<pair<int64, int>> stk = {{kInf64, 0}};
int64 sum = 0;
//left to right
for (int i = L[query]; i <= R[query]; i++) {
int cnt = 1;
while (stk.back().first <= H[i]) {
const auto &[h, c] = stk.back();
cnt += c;
sum -= h * 1LL * c;
stk.pop_back();
}
stk.emplace_back(H[i], cnt);
sum += H[i] * 1LL * cnt;
cost[i] += sum;
}
stk = {{kInf64, 0}};
sum = 0;
//right to left
for (int i = R[query]; i >= L[query]; i--) {
int cnt = 1;
while (stk.back().first <= H[i]) {
const auto &[h, c] = stk.back();
cnt += c;
sum -= h * 1LL * c;
stk.pop_back();
}
stk.emplace_back(H[i], cnt);
sum += H[i] * 1LL * cnt;
cost[i] += sum;
}
//store the answer
ans[query] = *min_element(cost.begin() + L[query], cost.begin() + R[query] + 1);
}
return ans;
}
