#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
int q = L.size();
int n = h.size();
vector<long long>ansr(q);
for(int i = 0;i<q;i++){
long long ans[n];
fill(ans,ans+n,0);
set<array<int,2>>s;
for(int j = L[i];j<=R[i];j++){
auto it = s.lower_bound({h[j],-1});
if(s.size()&&it!=s.end()){
array<int,2>a = *it;
ans[j]+=ans[a[1]]+1LL*h[j]*(j-a[1]);
}
else{
ans[j]+=1LL*h[j]*(j+1-L[i]);
}
while(s.size()&&(*s.begin())[0]<=h[j]){
s.erase(s.begin());
}
s.insert({h[j],j});
}
s.clear();
long long cans[n];
fill(cans,cans+n,0);
for(int j = R[i];j>=L[i];j--){
auto it = s.lower_bound({h[j],-1});
if(s.size()&&it!=s.end()){
array<int,2>a = *it;
ans[j]+=cans[a[1]]+1LL*h[j]*(a[1]-j-1);
cans[j]=cans[a[1]]+1LL*h[j]*(a[1]-j);
}
else{
ans[j]+=1LL*h[j]*(R[i]-j);
cans[j]=1LL*h[j]*(R[i]-j+1);
}
while(s.size()&&(*s.begin())[0]<=h[j]){
s.erase(s.begin());
}
s.insert({h[j],j});
}
ansr[i]=2e18;
for(int j = L[i];j<=R[i];j++){
ansr[i]=min(ansr[i],ans[j]);
}
}
return ansr;
}
