#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SZ(x) int((x).size())
#define lc id << 1
#define rc lc | 1
const ll MAXN = 5010;
const ll LOG = 22;
const ll INF = 1e18;
ll n , q , A[MAXN] , dpl[MAXN][MAXN] , dpr[MAXN][MAXN];
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = SZ(H); q = SZ(L);
if(n > MAXN){
return {};
}
for(int i = 0 ; i < n ; i++){
A[i] = H[i];
}
for(int i = 0 ; i < n ; i++){
ll mx = A[i];
for(int j = i + 1 ; j < n ; j++){
mx = max(mx , A[j]);
dpl[i][j] = dpl[i][j - 1] + mx;
}
}
for(int i = 0 ; i < n ; i++){
ll mx = A[i];
for(int j = i ; j >= 0 ; j--){
mx = max(mx , A[j]);
dpr[i][j] = dpr[i][j + 1] + mx;
}
}
vector<ll> ans(q , 0);
for(int i = 0 ; i < q ; i++){
ll res = INF;
for(int j = L[i] ; j <= R[i] ; j++){
res = min(res , dpr[j][L[i]] + dpl[j][R[i]]);
}
ans[i] = res;
}
return ans;
}
