#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define K 5010
long long gol[K][K],gor[K][K];
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
int Q=L.size(),N=H.size();
vector<long long>C(Q),h;
for(auto i:H)h.push_back(i);
for(int i=0;i<N;i++)
gol[i][i]=gor[i][i]=H[i];
for(int i=0;i<N;i++)
for(int j=i+1;j<N;j++)
gor[i][j]=max(gor[i][j-1],h[j]);
for(int i=0;i<N;i++)
for(int j=i-1;~j;j--)
gol[i][j]=max(gol[i][j+1],h[j]);
for(int i=0;i<N;i++)
for(int j=i+1;j<N;j++)
gor[i][j]+=gor[i][j-1];
for(int i=0;i<N;i++)
for(int j=i-1;~j;j--)
gol[i][j]+=gol[i][j+1];
for (int i=0;i<Q;i++) {
C[i]=1e18;
for(int j=L[i];j<=R[i];j++)
C[i]=min(C[i],gol[j][L[i]]+gor[j][R[i]]-H[j]);
}
return C;
}
