#include <iostream>
#include <vector>
using namespace std;
const int Sz = 5005;
long long Sum1[Sz][Sz], Sum2[Sz][Sz];
vector<long long> minimum_costs(vector<int> h, vector<int> L, vector<int> R){
int n = h.size();
for (int i=0;i<n;i++){
int mx = 0;
for (int j=i;j>=0;j--)
mx = max(mx, h[j]), Sum1[j][i] = Sum1[j+1][i] + mx;
mx = 0;
for (int j=i;j< n;j++)
mx = max(mx, h[j]), Sum2[i][j] = Sum2[i][max(0, j-1)] + mx;
}
vector<long long> Ans;
for (int i=0;i<L.size();i++){
long long ans = 1e15;
for (int j=L[i];j<=R[i];j++)
ans = min(ans, Sum1[L[i]][j] + Sum2[j][R[i]] - h[j]);
Ans.push_back(ans);
}
return Ans;
}
