#include "bits/stdc++.h"
using namespace std;
vector<vector<int>>mp(3005,vector<int>(3005));
long long sol(int x, vector<int> &h, int l, int r)
{
long long ac=0;
for(int i=l; i<=r; i++){
ac+=mp[i][x];
}
return ac;
}
void init(vector<int> &h, int n)
{
for(int i=0; i<n; i++){
int mx=0;
for(int j=i; j<n; j++){
mx=max(mx,h[j]);
mp[i][j]=mp[j][i]=mx;
}
}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
vector<long long>ans;
int n=(int)H.size(),q=(int)L.size();
assert(n*n*q<1e8);
init(H,n);
for(int i=0; i<q; i++){
long long mn=1e18;
for(int x=L[i]; x<=R[i]; x++){
long long ts=sol(x,H,L[i],R[i]);
mn=min(ts,mn);
}
ans.push_back(mn);
}
return ans;
}
// signed main(){
// for(auto c:minimum_costs({1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000},{0,3},{5,8}))cout<<c<<' ';
// }
