#include "meetings.h"
#include<cstdio>
#include<iostream>
#include<vector>
#define N 5005
typedef long long ll;
using namespace std;
ll n, Q, mx[N][N], s[N][N], h[N], l[N], r[N];
vector<ll> ans;
ll f(ll p, ll q) {
if (q < 0) return 0;
return s[p][q];
}
std::vector<long long> minimum_costs(std::vector<int> hh, std::vector<int> lll,
std::vector<int> rr) {
ll i, j, x, mn;
n = hh.size();
Q = lll.size();
for (i = 0; i < n; i++) {
h[i] = hh[i];
}
for (i = 0; i < Q; i++) {
l[i] = lll[i];
r[i] = rr[i];
}
for (i = 0; i < n; i++) {
mx[i][i] = h[i];
for (j = i - 1; j >= 0; j--) {
mx[i][j] = max(mx[i][j + 1], h[j]);
}
for (j = i +1; j < n; j++) {
mx[i][j] = max(mx[i][j - 1], h[j]);
}
s[i][0] = mx[i][0];
for (j = 1; j < n; j++) s[i][j] = s[i][j - 1] + mx[i][j];
}
for (i = 0; i < Q; i++) {
mn = -1;
for (j = 0; j < n; j++) {
x = f(j, r[i]) - f(j, l[i] - 1);
if (mn == -1 || x < mn) mn = x;
}
ans.push_back(mn);
}
return ans;
}
