#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;
typedef vector<ll> vl;
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define bk back()
#define ins insert
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
const ll INF = 1e18;
void ckmax(int& a, int b){
a = max(a, b);
}
void ckmin(ll& a, ll b){
a = min(a, b);
}
const int MOD = 1e9+7;
const int mx = 100005;
mt19937 rng(127);
int N, Q;
struct BIT{
ll BT[5005];
void upd(int pos, ll val){
pos++;
for(int i = pos; i < 5005; i+=i&-i){
// cout << i << "\n";
// cout.flush();
BT[i]+=val;
}
}
ll sum(int pos){
ll res = 0;
for(int i = pos; i > 0; i-=i&-i){
// cout << i << "\n";
// cout.flush();
res+=BT[i];
}
return res;
}
ll query(int l, int r){
l++;
r++;
return sum(r)-sum(l-1);
}
};
BIT bt[5005];
vl minimum_costs(vi H, vi L, vi R) {
// cout << "HI" << "\n";
// cout.flush();
N = sz(H);
Q = sz(L);
for(int i = 0; i < N; i++){
bt[i].upd(i, H[i]);
int cur_max = H[i];
for(int j = i-1; j >= 0; j--){
ckmax(cur_max, H[j]);
bt[i].upd(j, cur_max);
}
cur_max = H[i];
for(int j = i+1; j < N; j++){
ckmax(cur_max, H[j]);
bt[i].upd(j, cur_max);
// cout << "building: " << i << " " << j << " " << cur_max << "\n";
}
}
// for(int i = 0; i < N; i++){
// for(int j = 0; j < N; j++){
// cout << i << " " << j << " " << bt[i].query(j, j) << "\n";
// }
// }
vl C(Q, INF);
for(int i = 0; i < Q; i++){
ll ans = INF;
for(int j = L[i]; j <= R[i]; j++){
ckmin(ans, bt[j].query(L[i], R[i]));
}
C[i] = ans;
}
return C;
}
