#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define X first
#define Y second
using namespace std;
ll ez(int l, int r, vector<int>& H){
vector<ll> le, ri, st, am;
le.assign(H.size(), 0);
ri.assign(H.size(), 0);
ll cur = 0;
for(int i = l; i<=r; i++){
ll tmp = 1;
while(st.size()>0 && st.back() <= H[i]){
tmp+=am.back();
cur-=am.back()*st.back();
st.pop_back();
am.pop_back();
}
cur+=tmp*H[i];
le[i] = cur;
st.pb((ll)H[i]);
am.pb(tmp);
}
cur = 0;
st.clear(); am.clear();
for(int i = r; i>=l; i--){
ll tmp = 1;
while(st.size()>0 && st.back() <= H[i]){
tmp+=am.back();
cur-=am.back()*st.back();
st.pop_back();
am.pop_back();
}
cur+=tmp*H[i];
ri[i] = cur;
st.pb((ll)H[i]);
am.pb(tmp);
}
ll ret = 1e15;
for(int i = l; i<=r; i++){
ret = min(ret, le[i]+ri[i]-H[i]);
}
return ret;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
int Q = L.size();
vector<ll> C(Q);
for (int j = 0; j < Q; ++j) {
C[j] = ez(L[j], R[j], H);
}
return C;
}
