#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int N;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
N = H.size();
int Q = L.size();
vector<ll> C(Q, 1ll<<50);
for (int i=0; i<Q; i++){
vector<ll> lc(N, 0), rc(N, 0);
stack<pair<ll,pair<ll,ll>>> s;
for (int j=L[i]; j<=R[i]; j++){
lc[j] = H[j];
if (j != L[i]) lc[j] += lc[j-1];
while (!s.empty() && H[j] > s.top().first){
lc[j] += ((ll) H[j]-s.top().first)*s.top().second.first;
s.pop();
}
if (s.empty()) s.push({H[j], {j-L[i]+1, j}});
else s.push({H[j], {j-s.top().second.second, j}});
}
while (!s.empty()) s.pop();
for (int j=R[i]; j>=L[i]; j--){
rc[j] = H[j];
if (j != R[i]) rc[j] += rc[j+1];
while (!s.empty() && H[j] > s.top().first){
rc[j] += ((ll) H[j]-s.top().first)*s.top().second.first;
s.pop();
}
if (s.empty()) s.push({H[j], {R[i]-j+1, j}});
else s.push({H[j], {s.top().second.second-j, j}});
}
for (int j=L[i]; j<=R[i]; j++) C[i] = min(C[i], lc[j]+rc[j]-H[j]);
}
return C;
}
