#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int MAX_N = 5e3 + 5;
i64 r[MAX_N][MAX_N];
i64 l[MAX_N][MAX_N];
vector<i64> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
const int n = H.size();
const int q = L.size();
vector<i64> C(q);
for (int i = 0; i < n; i++) {
int mx;
mx = H[i];
for (int j = i + 1; j < n; j++) {
mx = max(mx, H[j]);
r[i][j] = r[i][j - 1] + mx;
}
mx = H[i];
l[i][i] = mx;
for (int j = i - 1; ~j; j--) {
mx = max(mx, H[j]);
l[i][j] = l[i][j + 1] + mx;
}
}
for (int i = 0; i < q; i++) {
const int lo = L[i];
const int hi = R[i];
i64 mn = 1e18;
for (int j = lo; j <= hi; j++) {
i64 left_side = l[j][lo];
i64 right_side = r[j][hi];
mn = min(mn, left_side + right_side);
}
C[i] = mn;
}
return C;
}
