#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> A;
long long solve(vector<int> &a) {
int n = (int)a.size();
vector<long long> lc(n), rc(n);
vector<pair<long long, long long>> vals; // {value, index}
for (int i = 0; i < n; i++) vals.push_back({a[i], i});
sort(vals.begin(), vals.end()); reverse(vals.begin(), vals.end());
set<int> in; in.insert(-1); in.insert(n);
long long ans = 1e18;
for (auto &vl : vals) {
long long v = vl.first; int i = vl.second;
auto lftit = in.lower_bound(i); lftit--;
int lft = *lftit;
auto rgtit = in.upper_bound(i); int rgt = *rgtit;
lc[i] = (long long)(i - lft) * v + (lft != -1 ? lc[lft] : (long long)0);
rc[i] = (long long)(rgt - i) * v + (rgt != n ? rc[rgt] : (long long)0);
ans = min(ans, lc[i] + rc[i] - a[i]);
in.insert(i);
}
return ans;
}
vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
int Q = (long long)L.size(); vector<long long> ans(Q);
int N = (int)H.size(); A.resize(N); for (int i = 0; i < N; i++) A[i] = H[i];
for (int j = 0; j < Q; ++j) {
vector<int> b; for (int i = L[j]; i <= R[j]; i++) b.push_back(H[i]);
ans[j] = solve(b);
}
return ans;
}
