#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
long long N, Q, H[5009], T[5009]; pair<int, int> dp[5009][5009];
void dfs(int cl, int cr) {
if (cl > cr) return;
int cm = dp[cl][cr].second; long long cost = dp[cl][cr].first;
//cout << "cl = " << cl << ", cr = " << cr << ", cm = " << cm << ", cost = " << cost << endl;
T[cl] += cost * (cr - cm + 1);
T[cm] += cost * (cm - cl);
T[cm + 1] -= cost * (cr - cm);
T[cr + 1] -= cost * (cm - cl + 1);
dfs(cl, cm - 1);
dfs(cm + 1, cr);
}
vector<long long> minimum_costs(vector<int> HH, vector<int> L, vector<int> R) {
N = HH.size(); Q = L.size();
for (int i = 0; i < N; i++) H[i] = HH[i];
for (int i = 0; i < N; i++) {
pair<int, int> BASE = make_pair(-1, -1);
for (int j = i; j < N; j++) {
BASE = max(BASE, make_pair((int)H[j], j));
dp[i][j] = BASE;
}
}
vector<long long> ans;
for (int i = 0; i < Q; i++) {
for (int j = 0; j <= N; j++) T[j] = 0;
dfs(L[i], R[i]);
for (int j = 1; j <= N; j++) T[j] += T[j - 1];
long long rem = (1LL << 60);
for (int j = L[i]; j <= R[i]; j++) rem = min(rem, T[j]);
ans.push_back(rem);
}
return ans;
}
