#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
long long A[5001], lc[5001], rc[5001];
pair<long long, long long> vals[5001];
long long a[5001];
long long solve(int n) {
for (int i = 0; i < n; i++) vals[i] = {a[i], i};
for (int i = n; i < 5001; i++) vals[i] = {-1e18, -1e18};
sort(vals, vals + 5001); reverse(vals, vals + 5001);
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;
if (v == -1e18) break;
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(); for (int i = 0; i < N; i++) A[i] = H[i];
for (int j = 0; j < Q; ++j) {
for (int i = L[j]; i <= R[j]; i++) a[i - L[j]] = A[i];
ans[j] = solve(R[j] - L[j] + 1);
}
return ans;
}
