#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int N = H.size();
vector mx(N, vector<pii>(N));
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
if (i == j)
mx[i][j] = {H[i], i};
else
mx[i][j] = max(mx[i][j - 1], {H[j], j});
}
}
vector dp(N, vector<ll>(N));
for (int l = 0; l < N; l++) {
for (int i = 0; i + l < N; i++) {
int j = i + l;
auto [m, k] = mx[i][j];
dp[i][j] = 1ll * m * (l + 1);
if (i < k)
dp[i][j] = min(dp[i][j], dp[i][k - 1] + 1ll * m * (j - k + 1));
if (k < j)
dp[i][j] = min(dp[i][j], dp[k + 1][j] + 1ll * m * (k - i + 1));
}
}
int Q = L.size();
vector<ll> res(Q);
for (int i = 0; i < Q; i++)
res[i] = dp[L[i]][R[i]];
return res;
}
/*
4 2
2 4 3 5
0 2
1 3
*/
