#include "bits/stdc++.h"
using namespace std;
vector<vector<int>>mp(1005,vector<int>(1005));
int sol(int x, vector<int> &h, int l, int r)
{
int ac=0;
for(int i=l; i<=r; i++){
int mx=mp[min(i,x)][max(i,x)];
ac+=mx;
}
return ac;
}
void init(vector<int> &h, int n)
{
for(int i=0; i<n; i++){
int mx=h[i];
for(int j=i; j<n; j++){
mx=max(mx,h[j]);
mp[i][j]=mx;
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++){
int mn=1e9;
for(int x=0; x<n; x++){
int ts=sol(x,H,L[i],R[i]);
if(ts<mn)mn=ts;
}
ans.push_back(mn);
}
return ans;
}
// signed main(){
// for(auto c:minimum_costs({2,4,3,5},{0,1},{2,3}))cout<<c<<' ';
// }
