#include "meetings.h"
#include <bits/stdc++.h>
#define uwu return
#define fs first
#define sc second
using namespace std;
vector<long long> H;
const int SIZE = 5e3 + 5;
long long pr[SIZE], pl[SIZE];
long long calc(int l, int r){
l++, r++;
vector<pair<long long, long long>> mono_stk;
mono_stk.push_back({1e9 + 5, r + 1});
pl[l - 1] = 0, pr[r + 1] = 0;
for (long long i = r; i >= l; i--){
pr[i] = pr[i + 1];
while (mono_stk.back().fs < H[i]){
pair <long long, long long> tmp = mono_stk.back();
mono_stk.pop_back();
pr[i] -= (mono_stk.back().sc - tmp.sc) * tmp.fs;
}
pr[i] += (mono_stk.back().sc - i) * H[i];
mono_stk.push_back({H[i], i});
}
mono_stk.clear();
mono_stk.push_back({1e9 + 5, l - 1});
for (long long i = l; i <= r; i++){
pl[i] = pl[i - 1];
while (mono_stk.back().fs < H[i]){
pair <long long, long long> tmp = mono_stk.back();
mono_stk.pop_back();
pl[i] -= (tmp.sc - mono_stk.back().sc) * tmp.fs;
}
pl[i] += (i - mono_stk.back().sc) * H[i];
mono_stk.push_back({H[i], i});
}
long long ret = 1e18;
for (int i = l; i <= r; i++){
ret = min(ret, pl[i] + pr[i] - H[i]);
}
return ret;
}
vector<long long> minimum_costs(vector<int> _H, vector<int> L, vector<int> R) {
int Q = L.size();
H.push_back(0);
for (auto i : _H){
H.push_back(i);
}
vector<long long> C(Q);
for (int i = 0; i < Q; i++){
C[i] = calc(L[i], R[i]);
}
return C;
}
