#include "meetings.h"
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
// #define int ll
using namespace std;
using ll = long long;
const ll N = 5555 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
ll pr[N][N] , sf[N][N] , a[N];
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = L.size();
int n = H.size();
vector<long long> C(Q);
for(int i = 1; i <= n; i++){
a[i] = H[i-1];
}
for(int l = 1; l <= n; l++){
ll mx = a[l];
for(int r = l; r <= n; r++){
mx = max(mx , a[r]);
pr[l][r] = pr[l][r-1] + mx;
}
}
for(int r = n; r >= 1; r--){
ll mx = a[r];
for(int l = r; l >= 1; l--){
mx = max(mx , a[l]);
sf[r][l] = sf[r][l+1] + mx;
}
}
for(int i = 0; i < Q; i++){
L[i]++;
R[i]++;
C[i] = INF;
for(int j = L[i]; j <= R[i]; j++){
C[i] = min(C[i] , pr[j][R[i]]+sf[j][L[i]]-a[j]);
}
}
return C;
}
