#include "meetings.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, q;
vector<ll> H;
vector<int> L, R;
vector<ll> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R){
int n = _H.size(), q = _L.size();
for(int i = 0; i < n; i++) H.pb(_H[i]);
swap(L, _L), swap(R, _R);
vector<ll> ans(q);
for(int qi = 0; qi < q; qi++){
int l = L[qi], r = R[qi];
vector<ll> costs(r-l+1, 0);
stack<pair<ll, int>> st;
ll c = 0;
for(int i = l; i <= r; i++){
while(!st.empty() && st.top().f <= H[i]){
auto [h, j] = st.top();
st.pop();
if(st.empty()) c-=h*(j-l+1);
else c-=h*(j-st.top().sc);
}
if(st.empty()) c+=H[i]*(i-l+1);
else c+=H[i]*(i-st.top().sc);
st.push({H[i], i});
costs[i-l]+=c;
}
while(!st.empty()) st.pop();
c = 0;
for(int i = r; i >= l; i--){
while(!st.empty() && st.top().f <= H[i]){
auto [h, j] = st.top();
st.pop();
if(st.empty()) c-=h*(r-j+1);
else c-=h*(st.top().sc-j);
}
if(st.empty()) c+=H[i]*(r-i+1);
else c+=H[i]*(st.top().sc-i);
st.push({H[i], i});
costs[i-l]+=c;
costs[i-l]-=H[i];
}
ans[qi] = *min_element(costs.begin(), costs.end());
}
return ans;
}
