#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18L + 20;
long long sum_l[5020][5020];
long long sum_r[5020][5020];
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = H.size();
int Q = L.size();
if (N <= 5000) {
for (int i = 0; i < N; i++) {
int mx = 0;
long long sum = 0;
for (int j = i; j >= 0; j--) {
mx = max(mx, H[j]);
sum += mx;
sum_l[j][i] = sum;
}
mx = 0;
sum = 0;
for (int j = i; j < N; j++) {
mx = max(mx, H[j]);
sum += mx;
sum_r[i][j] = sum;
}
}
vector<long long> res(Q, inf);
for (int i = 0; i < Q; i++) {
for (int j = L[i]; j <= R[i]; j++) {
res[i] = min(res[i], sum_l[L[i]][j] + sum_r[j][R[i]] - H[j]);
}
}
return res;
}
return vector<long long>();
}
