#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
int N,Q;
long long A[5001],B[5001];
vector<long long> minimum_costs(vector<int>H,vector<int>L,vector<int>R){
N=H.size();
Q=L.size();
assert(N<=5000&&Q<=5000);
vector<long long>res(Q);
for(int i=0;i<Q;i++){
map<int,int>mp;
long long t=0;
for(int j=0;j<N;j++){
A[j]=B[j]=0;
}
for(int j=L[i];j<=R[i];j++){
t+=H[j];
mp[H[j]]++;
while(mp.begin()->first<H[j]){
t+=(H[j]-mp.begin()->first)*(long long)mp.begin()->second;
mp[H[j]]+=mp.begin()->second;
mp.erase(mp.begin());
}
A[j]=t;
}
t=0;
mp.clear();
for(int j=R[i];j>=L[i];j--){
t+=H[j];
mp[H[j]]++;
while(mp.begin()->first<H[j]){
t+=(H[j]-mp.begin()->first)*(long long)mp.begin()->second;
mp[H[j]]+=mp.begin()->second;
mp.erase(mp.begin());
}
B[j]=t;
}
long long a=0xE869120E869120;
for(int j=L[i]-1;j<=R[i];j++){
if(j==-1){
a=min(a,B[j+1]);
}
else if(j==N-1){
a=min(a,A[j]);
}
else{
a=min(a,A[j]+B[j+1]);
}
}
res[i]=a;
}
return res;
}
