#include "meetings.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> vs[25];
const int maxn=750005;
typedef pair<int,int>pi;
map<pi,int>mp;
const int oo = 1'000'000'000'000'000'000ll;
vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L,
vector<int32_t> R) {
int n=H.size();
for(int i=0;i<n;i++){
vs[H[i]].push_back(i);
}
for(int i=0;i<n;i++){
//cerr<<i<<":\n";
vector<pi>vidx;
for(int k=1;k<=20;k++){
auto it=upper_bound(vs[k].begin(),vs[k].end(),i);
if(it!=vs[k].begin()){
vidx.push_back({*prev(it),k}); // {index, value from this point onwards}
}
}
sort(vidx.begin(),vidx.end(),greater<pi>());
int cur=H[i];
int sum=0;
int lst=i;//covered including this idx
vector<pi> ls,rs;
ls.push_back({i,0});
rs.push_back({i,0});
for(auto x:vidx){
if(x.second>cur){
sum += (lst-x.first-1)*cur + x.second;
cur=x.second;
lst=x.first;
ls.push_back({x.first,sum});
}
}
vidx.clear();
for(int k=1;k<=20;k++){
auto it=lower_bound(vs[k].begin(),vs[k].end(),i);
if(it!=vs[k].end()){
vidx.push_back({*it,k});
}
}
sort(vidx.begin(),vidx.end());
cur=H[i];
sum=0;
lst=i;
for(auto x:vidx){
if(x.second>cur){
sum += (x.first-lst-1)*cur + x.second;
cur=x.second;
lst=x.first;
rs.push_back({x.first,sum});
}
}
for(auto x:ls){
for(auto y:rs){
int lf=x.first;
int rg=y.first;
if(lf>rg)continue;
int su=x.second+y.second+H[i];
if(mp.find({lf,rg}) == mp.end() || mp[{lf,rg}]>su){
//cerr<<lf<<","<<rg<<":"<<su<<endl;
mp[{lf,rg}]=su;
}
}
}
}
int Q=L.size();
vector<int> res;
for(int i=0;i<Q;i++){
int S=L[i],E=R[i];
vector<pi>lf,rg;
for(int k=1;k<=20;k++){
auto it=lower_bound(vs[k].begin(),vs[k].end(),S);
if(it!=vs[k].end() && *it <= E){
lf.push_back({*it,k});
}
}
for(int k=1;k<=20;k++){
auto it=upper_bound(vs[k].begin(),vs[k].end(),E);
if(it!=vs[k].begin() && *prev(it) >= S){
rg.push_back({*prev(it),k});
}
}
sort(lf.begin(),lf.end());
sort(rg.begin(),rg.end(),greater<pi>());
vector<pi>L,R;
for(auto x:lf){
if(L.empty() || x.second > L.back().second){
L.push_back(x);
}
}
for(auto x:rg){
if(R.empty() || x.second > R.back().second){
R.push_back(x);
}
}
int ans=oo;
for(auto x:L){
for(auto y:R){
if(x.first<=y.first){
//cerr<<x.first<<" "<<y.first<<endl;
if(mp.find({x.first,y.first}) != mp.end()){
ans=min(ans,mp[{x.first,y.first}] + (x.first-S)*x.second+(E-y.first)*y.second);
}
}
}
}
res.push_back(ans);
}
return res;
}
