#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const ll INF = 1e18;
const int N = 5005;
int dp[N][N], opt[N][N];
ll lp[N][N], rp[N][N];
std::vector<long long> minimum_costs(std::vector<int> a, std::vector<int> L,
std::vector<int> R) {
int n = a.size(), q = L.size();
for (int i = 0; i < n; i++) {
ll cur = 0;
int mx = a[i];
for (int j = i - 1; j >= 0; j--) {
mx = max(mx, a[j]);
cur += mx;
lp[j][i] = cur;
}
cur = 0;
mx = a[i];
for (int j = i + 1; j < n; j++) {
mx = max(mx, a[j]);
cur += mx;
rp[i][j] = cur;
}
dp[i][i] = a[i];
opt[i][i] = i;
}
// cout << rp[0][2] << "\n";
// return vector<ll>(q, 0);
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
ll val = INF;
int x = -1;
for (int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) {
ll cur = lp[i][k] + rp[k][j] + a[k];
if (cur < val) {
val = cur;
x = k;
}
}
opt[i][j] = x;
dp[i][j] = val;
}
}
vector<ll> ans(q);
for (int i = 0; i < q; i++) {
ll mn = INF;
for (int j = L[i]; j <= R[i]; j++) {
mn = min(mn, lp[L[i]][j] + rp[j][R[i]] + a[j]);
}
ans[i] = mn;
// ans[i] = dp[L[i]][R[i]];
}
return ans;
}
