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