// Be name khode //
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
typedef long long ll;
const int maxn5 = 5e3 + 4;
vector <ll> ret;
ll pre[maxn5][maxn5], suf[maxn5][maxn5];
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,
std::vector<int> r) {
int q = l.size();
int n = h.size();
for(int i = 0; i < n; i++){
int mx = h[i];
pre[i][i] = suf[i][i] = h[i];
for(int j = i + 1; j < n; j++){
mx = max(mx, h[j]);
pre[i][j] = pre[i][j - 1] + mx;
}
mx = h[i];
for(int j = i - 1; j >= 0; j--){
mx = max(mx, h[j]);
suf[i][j] = suf[i][j + 1] + mx;
}
}
for(int i = 0; i < q; i++){
ll mn = 1e18;
for(int j = l[i]; j <= r[i]; j++){
mn = min(mn, suf[j][l[i]] + pre[j][r[i]] - h[j]);
//cout << i << ' ' << j << ' ' << suf[j][l[i]] << ' ' << pre[j][r[i]] << endl;
}
ret.pb(mn);
}
return ret;
}
