#include "meetings.h"
#include <algorithm>
using namespace std;
#define sz(x) (int)x.size()
const long long INF = 1e18;
void calc(int x, vector<int>& H, vector<vector<long long>>& pref, vector<vector<long long>>& suff) {
long long hi;
pref[x][x] = H[x];
hi = H[x];
for(int i=x-1; i>=0; i--) {
hi = max(hi, (long long)H[i]);
pref[x][i] = pref[x][i+1] + hi;
}
if(x+1 < sz(H)) {
suff[x][x+1] = H[x+1];
hi = H[x+1];
for(int i=x+2; i<sz(H); i++) {
hi = max(hi, (long long)H[i]);
suff[x][i] = suff[x][i-1] + hi;
}
}
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = sz(L);
vector<vector<long long>> pref(sz(H), vector<long long>(sz(H)));
vector<vector<long long>> suff(sz(H), vector<long long>(sz(H)));
for(int x=0; x<sz(H); x++) calc(x, H, pref, suff);
vector<long long> ret(Q, INF);
for(int i=0; i<Q; i++) {
for(int x=L[i]; x<=R[i]; x++) {
if(x != R[i])
ret[i] = min(ret[i], pref[x][L[i]] + suff[x][R[i]]);
else
ret[i] = min(ret[i], pref[x][L[i]]);
}
}
return ret;
}
