#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long int64;
const int maxn = 5e3 + 2;
const int lg = 13;
int sp[maxn][lg];
int64 dp[maxn][maxn];
int query (int l, int r) {
int k = log2(r - l + 1);
return max(sp[l][k], sp[r - (1 << k) + 1][k]);
}
vector<int64> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
int Q = L.size();
int n = H.size();
vector<int64> C(Q);
for (int i = 1; i <= n; i++) {
sp[i][0] = H[i - 1];
}
for (int k = 1; k < lg; k++){
for (int i = 1; i + (1 << k) - 1 <= n; i++){
sp[i][k] = max(sp[i][k-1], sp[i + (1 << (k - 1))][k-1]);
}
}
for (int i = 1; i <= n; i++){ // dp[l][r] -> suma toate query(l, l <= i <= r)
dp[i][i] = H[i - 1];
for (int j = i + 1; j <= n; j++){
dp[i][j] = dp[i][j-1] + query(i, j);
}
}
for (int i = n; i >= 1; i--){ // dp[r][l] -> suma toate query(l <= i <= r, r)
for (int j = i - 1; j >= 1; j--){
dp[i][j] = dp[i][j + 1] + query(j, i);
}
}
// for (int i = 1; i <= n; i++){
// for (int j = 1; j <= n; j++){
// cout << i << " " << j << " " << dp[i][j] << "\n";
// }
// }
for (int i = 0; i < Q; i++){
L[i]++;
R[i]++;
int64 ans = min(dp[L[i]][R[i]], dp[R[i]][L[i]]);
for (int j = L[i]; j < R[i]; j++){
ans = min(ans, dp[j][L[i]] + dp[j + 1][R[i]]);
}
C[i] = ans;
}
return C;
}
