#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e3 + 10;
ll FL[MAXN][MAXN], FR[MAXN][MAXN];
vector<ll> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
int Q = L.size();
int n = H.size();
vector<ll> ans(Q);
for (int x = 0; x < n; x++) {
ll mx = H[x];
FL[x][x] = FR[x][x] = mx;
for (int i = x - 1; i >= 0; i--) {
mx = max(mx, ll(H[i]));
FL[i][x] = FL[i + 1][x] + mx;
}
mx = H[x];
for (int i = x + 1; i < n; i++) {
mx = max(mx, ll(H[i]));
FR[i][x] = FR[i - 1][x] + mx;
}
}
for (int i = 0; i < Q; i++) {
ans[i] = numeric_limits<ll>::max();
for (int x = L[i]; x <= R[i]; x++)
ans[i] = min(ans[i], FL[L[i]][x] + FR[R[i]][x] - H[x]);
}
return ans;
}
