#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
int n = H.size();
if(ll(n)*Q <= 1e8){
vector<ll> resp(Q);
vector<ll> val(n);
for(int q = 0; q < Q; q++){
fill(val.begin()+L[q],val.begin()+R[q]+1,0);
ll cur = 0;
vector<pll> st;
for(int i = L[q]; i <= R[q]; i++){
ll ct = 1;
while(!st.empty() && st.back().ff <= H[i]){
cur-=st.back().ff*st.back().ss;
ct+=st.back().ss;
st.pop_back();
}
cur+=ct*H[i];
st.push_back({H[i],ct});
val[i]+=cur;
}
st.clear();
cur = 0;
for(int i = R[q]; i >= L[q]; i--){
val[i]+=cur;
ll ct = 1;
while(!st.empty() && st.back().ff <= H[i]){
cur-=st.back().ff*st.back().ss;
ct+=st.back().ss;
st.pop_back();
}
cur+=ct*H[i];
st.push_back({H[i],ct});
}
resp[q] = *min_element(val.begin()+L[q],val.begin()+R[q]+1);
}
return resp;
}
return vector<ll>(1,-1);
}
