#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
const ll INF = 1LL<<60;
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
int n = (int)h.size();
int q = (int)l.size();
vector<ll> ans(q, INF);
vector<vector<ll>> side_cost(n, vector<ll>(n));
for (int i = 0; i < n; ++i) {
for (int j = i+1, mx = h[i]; j < n; ++j) {
mx = max(mx, h[j]);
side_cost[i][j] = side_cost[i][j-1] + mx;
}
for (int j = i-1, mx = h[i]; j >= 0; --j) {
mx = max(mx, h[j]);
side_cost[i][j] = side_cost[i][j+1] + mx;
}
}
auto solve = [&](int i, int l, int r) {
ll ans = h[i];
if (l < i) ans += side_cost[i][l];
if (r > i) ans += side_cost[i][r];
return ans;
};
for (int qq = 0; qq < q; ++qq) {
for (int i = l[qq]; i <= r[qq]; ++i)
ans[qq] = min(ans[qq], solve(i, l[qq], r[qq]));
}
return ans;
}
