#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pi = pair<int,int>;
const int MOD = 1e9 + 7;
#define F first
#define S second
#define sz(x) int((x).size())
#define sor(x) sort(begin(x), end(x))
#define FOR(i, a, b) for (int i = a; i < b; i++)
vi H, L, R;
vector<vl> Maxes, Prefix, Suffix;
vl prefix(vl A) {
int k = sz(A);
ll mx = 0, s = 0;
vl Maxes, Pref;
FOR(i, 0, k) {
mx = max(A[i], mx);
Maxes.push_back(mx);
}
FOR(i, 0, k) {
s += Maxes[i];
Pref.push_back(s);
}
return Pref;
}
vl minimum_costs(vi H0, vi L0, vi R0) {
int n = H0.size(), q = L0.size();
for (auto h : H0) H.push_back(h);
for (auto l : L0) L.push_back(l);
for (auto r : R0) R.push_back(r);
vl Ans(q);
Maxes.resize(n, vl(n, 0));
Prefix.resize(n, vl(n, MOD));
Suffix.resize(n, vl(n, MOD));
FOR(l, 0, n) {
int mx = 0;
FOR(r, l, n) {
mx = max(mx, H[r]);
Maxes[l][r] = (ll)mx;
}
}
FOR(l, 0, n) {
Prefix[l][l] = Maxes[l][l];
FOR(r, l + 1, n) {
Prefix[l][r] = Prefix[l][r - 1] + Maxes[l][r];
}
}
FOR(r, 0, n) {
Suffix[r][r] = Maxes[r][r];
for (int l = r - 1; l >= 0; l--) {
Suffix[l][r] = Suffix[l + 1][r] + Maxes[l][r];
}
}
FOR(i, 0, q) {
int l = L[i], r = R[i];
ll Best = 1e18;
FOR(j, l, r + 1){
Best = min(Best, Suffix[l][j] + Prefix[j][r] - H[j]);
}
Ans[i] = Best;
}
//for (auto val : Ans) cout << val << " "; cout << "oink1 " << endl;
return Ans;
}
//#include "grader.cpp"
