#include <iostream>
#include "meetings.h"
long long mx[5100][5100], f[5100][5100];
long long upd1(long long a, long long b) {
return (a > b) ? a : b;
}
long long upd2(long long a, long long b) {
return (a < b) ? a : b;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
int n = (int)(H.size());
int q = (int)(L.size());
for (int i = 0; i < n; ++i)
mx[i][i] = H[i];
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
mx[i][j] = upd1(mx[j][j], mx[i][j - 1]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
mx[i][j] = mx[j][i];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
f[i][j] = (j - 1 < 0 ? 0 : f[i][j - 1]) + mx[i][j];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
std::cerr << i + 1 << " " << j + 1 << " " << mx[i][j] << " " << f[i][j] << "\n";
std::vector <long long> ret;
for (int _t = 0; _t < q; ++_t) {
std::cerr << L[_t] << " " << R[_t] << "\n";
long long res = (long long)(1e18);
for (int i = L[_t]; i <= R[_t]; ++i)
res = upd2(res, f[i][R[_t]] - (L[_t] - 1 < 0 ? 0 : f[i][L[_t] - 1]));
ret.push_back(res);
}
return ret;
}
