#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define pb push_back
#define F first
#define S second
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
typedef vector<ll> vl;
typedef vector<vl> vvl;
vl v;
struct Node{
Node *lnode, *rnode;
ll l, r;
Node(ll l, ll r) : l(l), r(r){
if(r-l==1){
}else{
}
}
};
ll rec(ll lo, ll hi){
if(hi-lo<=0) return 0;
if(hi-lo<=1) return v[lo];
ll maxval = 0;
for(int i = lo; i<hi; i++){
maxval= max(maxval, v[i]);
}
vl temp = {lo-1};
for(int i = lo; i<hi; i++){
if(v[i] == maxval) temp.pb(i);
}
temp.pb(hi);
ll ans = 1e18;
fo(i, ((ll)temp.size())-1){
ans = min(ans, (hi-lo-(temp[i+1]-temp[i]))*maxval+rec(temp[i]+1, temp[i+1]));
}
return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int q = L.size();
ll n = H.size();
vl C;
// fo(i, n) v.pb(H[i]);
// Node st(0, n);
fo(i, q){
v.clear();
for(ll j = L[i]; j<=R[i]; j++){
v.pb(H[j]);
}
C[i] = rec(0, v.size());
}
return C;
}
// int main(){
// // vector<int> a = {1, 1, 2, 1, 1, 1, 2, 2, 1};
// // vector<int> b = {0, 2};
// // vector<int> c = {5, 5};
// vector<int> a = {2, 4, 3, 5};
// vector<int> b = {0, 1};
// vector<int> c = {2, 3};
// minimum_costs(a, b, c);
// return 0;
// }
