#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
ll n=H.size();
ll Q = L.size();
vector<long long> C(Q);
vector<vector<ll>>dp(n,vector<ll>(n));
for(ll i=0;i<n;i++){
ll max_height=(ll)H[i];
dp[i][i]=max_height;
for(ll l=i-1;l>=0;l--){
max_height=max(max_height,(ll)H[l]);
dp[i][l]=(dp[i][l+1]+max_height);
}
max_height=H[i];
for(ll r=i+1;r<n;r++){
max_height=max(max_height,(ll)H[r]);
dp[i][r]=(dp[i][r-1]+max_height);
}
}
for(ll q=0;q<Q;q++){
C[q]=INT_MAX;
for(ll i=L[q];i<=R[q];i++){
C[q]=min(C[q],dp[i][L[q]]+dp[i][R[q]]-H[i]);
}
}
return C;
}
