#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define ll long long
// solving subtask 1 + 2 in O(N^2 + QN) time
const ll LLINF = 1ll<<60;
const int maxn = 5e3 + 10;
int n, q;
ll prefix[maxn][maxn] = {0};
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
n = H.size();
vector<ll> c;
for (int i = 0; i < n; i++){
// solving to right
int mx = H[i];
for (int j = i; j < n; j++){
mx = max(mx, H[j]);
prefix[j][i] = mx;
}
mx = H[i];
for (int j = i; j >= 0; j--){
mx = max(mx, H[j]);
prefix[j][i] = mx;
}
}
for (int i = 0; i < n; i++){
for (int j = 1; j < n; j++) prefix[i][j] += prefix[i][j - 1];
}
q = L.size();
c.assign(q, 0);
for (int i = 0; i < q; i++){
ll best = LLINF;
for (int j = L[i]; j <= R[i]; j++){
ll val = prefix[j][R[i]] - (L[i] == 0 ? 0 : prefix[j][L[i] - 1]);
best = min(best, val);
}
c[i] = best;
}
return c;
}
