#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5005;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int q = L.size();
vector<ll> ans(q);
for(int j=0;j<q;j++) {
ll a[maxn];
ll b[maxn];
stack<int> mp;
for(int i=L[j];i<=R[j];i++) {
while(!mp.empty() && H[mp.top()] < H[i]) {
mp.pop();
}
if(mp.empty()) {
a[i] = (ll)(i - L[j] + 1) * (ll)H[i];
}
else {
a[i] = (ll)(i - mp.top()) * (ll)H[i] + a[mp.top()];
}
mp.push(i);
}
while(!mp.empty()) {
mp.pop();
}
for(int i=R[j];i>=L[j];i--) {
while(!mp.empty() && H[mp.top()] < H[i]) {
mp.pop();
}
if(mp.empty()) {
b[i] = (ll)(R[j] - i + 1) * (ll)H[i];
}
else {
b[i] = (ll)(mp.top() - i) * (ll)H[i] + b[mp.top()];
}
mp.push(i);
}
ans[j] = a[L[j]] + b[L[j]] - H[L[j]];
for(int i=L[j];i<=R[j];i++) {
if(ans[j] > a[i] + b[i] - H[i]) {
ans[j] = a[i] + b[i] - H[i];
}
}
}
return ans;
}
