#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
long long ansLe[750005];
long long ansRi[750005];
map<int, int> mp;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R)
{
int Q = L.size();
std::vector<long long> C(Q);
for (int j = 0; j < Q; ++j)
{
int le=L[j], ri=R[j];
ansLe[le]=H[le];
mp.insert({H[le], 1});
for(int id=le+1; id<=ri; id++)
{
ansLe[id]=ansLe[id-1]+H[id];
map<int, int>::iterator it=mp.begin();
int br=1;
while((*it).first<H[id])
{
br+=(*it).second;
ansLe[id]+=(long long)(H[id]-(*it).first)*(*it).second;
mp.erase(it);
it=mp.begin();
if(mp.empty()) break;
}
if(!mp.empty() && mp.find(H[id])!=mp.end()) mp[H[id]]+=br;
else mp.insert({H[id], br});
}
mp.clear();
ansRi[ri]=H[ri];
mp.insert({H[ri], 1});
for(int id=ri-1; id>=le; id--)
{
ansRi[id]=ansRi[id+1]+H[id];
map<int, int>::iterator it=mp.begin();
int br=1;
while((*it).first<H[id])
{
br+=(*it).second;
ansRi[id]+=(H[id]-(*it).first)*(*it).second;
mp.erase(it);
it=mp.begin();
if(mp.empty()) break;
}
if(!mp.empty() && mp.find(H[id])!=mp.end()) mp[H[id]]+=br;
else mp.insert({H[id], br});
}
mp.clear();
C[j]=1e18;
for(int t=le; t<=ri; t++) if(C[j]>ansLe[t]+ansRi[t]-H[t]) C[j]=ansLe[t]+ansRi[t]-H[t];
}
return C;
}
