#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> solve(vector<int> H, vector<int> L, vector<int> R){
int N = H.size();
int Q = L.size();
vector<vector<int>> precomp(N, vector<int>(N));
vector<vector<ll>> prefix(N, vector<ll>(N + 1, 0));
// Compute minimums O(N^2)
for(int i = 0; i < N; i++){
precomp[i][i] = H[i];
int aCop = i + 1;
while(aCop < N){
precomp[i][aCop] = max(H[aCop], precomp[i][aCop - 1]);
aCop++;
}
int bCop = i - 1;
while(bCop >= 0){
precomp[i][bCop] = max(H[bCop], precomp[i][bCop + 1]);
bCop--;
}
}
// Calc prefixes O(N^2)
for(int i = 0; i < N; i++){
for(int j = 1; j <= N; j++){
prefix[i][j] = prefix[i][j - 1] + precomp[i][j - 1];
}
}
// Make queries O(N*Q)
vector<ll> C(Q);
for(int i = 0; i < Q; i++){
int l = L[i]; int r = R[i];
ll best = 1e18;
for(int j = l; j <= r; j++){
best = min(best, prefix[j][r + 1] - prefix[j][l]);
}
C[i] = best;
}
return C;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
return solve(H, L, R);
}
