#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
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();
vvll cost(N, vll(N));
rep(i, N) {
cost[i][i] = H[i];
int cmax = H[i];
for (int j = i - 1; j >= 0; j--) {
cmax = max(cmax, H[j]);
cost[i][j] = cost[i][j + 1] + cmax;
}
cmax = H[i];
ffor(j, i + 1, N) {
cmax = max(cmax, H[j]);
cost[i][j] = cost[i][j - 1] + cmax;
}
}
vll res(Q);
rep(i, Q) {
res[i] = 1LL << 62;
ffor(j, L[i], R[i] + 1) {
res[i] = min(res[i], cost[j][L[i]] + cost[j][R[i]] - H[j]);
}
}
return res;
}
