#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const long long MAXN = 5007;
int n, q;
long long cost[MAXN][MAXN];
vector<long long> ret;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
n = (int)H.size();
q = (int)L.size();
for(int i = 0; i < n; i++){
long long mx = H[i];
cost[i][i] = H[i];
for(int j = i + 1; j < n; j++){
mx = max(mx, (long long)H[j]);
cost[i][j] = cost[i][j - 1] + mx;
}
mx = H[i];
for(int j = i - 1; j >= 0; j--){
mx = max(mx, (long long)H[j]);
cost[i][j] = cost[i][j + 1] + mx;
}
}
for(int i = 0; i < q; i++){
int l = L[i], r = R[i];
long long ans = inf;
for(int j = l; j <= r; j++){
ans = min(ans, cost[l][j] + cost[r][j] - H[j]);
}
ret.push_back(ans);
}
return ret;
}
