#include <bits/stdc++.h>
using namespace std;
#include "meetings.h"
#define pb push_back
#define ll long long
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
vector<long long> sol;
for(int i=0;i<L.size();i++){
deque<pair<ll,ll>> dq;
ll sz=R[i]-L[i]+1;
ll pref[sz],ans=H[L[i]];
dq.pb({H[L[i]],1});
pref[0]=ans;
for(int j=L[i]+1;j<=R[i];j++){
ll cnt=1;
while(!dq.empty() && dq.back().first<=H[j]){
ans-=dq.back().second*dq.back().first;
cnt+=dq.back().second;
dq.pop_back();
}
dq.pb({H[j],cnt});
ans+=dq.back().first*dq.back().second;
pref[j-L[i]]=ans;
}
ans=H[R[i]];
dq.clear();
dq.pb({H[R[i]],1});
ll suff[sz],idx=sz-2;
suff[sz-1]=H[R[i]];
for(int j=R[i]-1;j>=L[i];j--){
ll cnt=1;
while(!dq.empty() && dq.front().first<=H[j]){
ans-=dq.front().second*dq.front().first;
cnt+=dq.front().second;
dq.pop_front();
}
dq.push_front({H[j],cnt});
ans+=dq.front().first*dq.front().second;
suff[idx]=ans;
idx--;
}
ll best=1e18,cnt=0;
for(int j=L[i];j<=R[i];j++){
// if(i==0 && j==L[i])cout<<pref[cnt]<<" "<<suff[cnt]<<endl;
best=min(best,pref[cnt]+suff[cnt]-H[j]);
cnt++;
}
sol.pb(best);
}
return sol;
}
