#include "meetings.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
ll ans[MAXN][MAXN];
int n;
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R){
n = h.size();
int Q = L.size();
for(int i=0;i<n;i++){
ll x = 0, res = 0;
for(int j=i;j<n;j++){
x = max(x, (ll)h[j]);
res += x;
ans[i][j] = res;
}
}
for(int i=0;i<n;i++){
ll x = 0, res = 0;
for(int j=i;j>=0;j--){
x = max(x, (ll)h[j]);
res += x;
ans[i][j] = res;
}
}
vector<ll> ret;
for(int q=0;q<Q;q++){
int l = L[q], r = R[q];
ll res = 1e18;
for(int i=l;i<=r;i++){
ll t = ans[i][l] + ans[i][r] - ans[i][i];
res = min(res, t);
}ret.push_back(res);
}return ret;
}
