#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC target("avx2,bmi,bmi2")
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
vector<ll> h(H.size());
for(int i = 0; i<H.size(); i++) h[i] = H[i];
vector<ll> sol(L.size());
for(int i = 0; i<L.size(); i++){
int l = L[i];
int r = R[i];
vector<array<ll, 2>> el(r-l+1);
for(int i = l; i<=r; i++) el[i-l] = {h[i], i};
sort(el.begin(), el.end());
ll sl = LONG_LONG_MAX;
set<array<ll, 3>> s;
for(int j = el.size()-1; j>=0; j--){
auto [hh, idx] = el[j];
//s.insert({idx, hh});
if(s.empty()){
sl = min(sl, hh*(r-l+1));
s.insert({idx, hh*(idx-l+1), hh*(r-idx+1)});
continue;
}
auto it = s.lower_bound({idx, hh});
ll left = 0;
ll right = 0;
if(it == s.begin()){
left = (idx-l+1)*hh;
}
else{
auto [ii, ll, rr] = *(--it);
left = ll + (idx-ii)*hh;
it++;
}
if(it == s.end()){
right = (r-idx+1)*hh;
}
else{
auto [ii, ll, rr] = *(it);
right = rr + (ii-idx)*hh;
}
s.insert({idx, left, right});
sl = min(sl, left+right-hh);
}
sol[i] = sl;
}
return sol;
}
