#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF LLONG_MAX
ll pre[5001][5001],suf[5001][5001];
ll cum[5001][5001],cum2[5001][5001];
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
int n=H.size();
for (int i = 0; i < n; ++i)
for (int j = i; j < n;++j)
{
pre[i][j]=H[j];
if(j)pre[i][j]=max(pre[i][j],pre[i][j-1]);
}
for (int i = n-1; i >= 0; i--)
for (int j = i; j >= 0;j--)
{
suf[i][j]=H[j];
if(j!=(n-1))suf[i][j]=max(suf[i][j],suf[i][j+1]);
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
{
cum2[i][j]+=suf[i][j];
if(i)cum2[i][j]+=cum2[i-1][j];
cum[i][j]+=pre[i][j];
if(i)cum[i][j]+=cum[i-1][j];
}
int Q = L.size();
vector<ll> C(Q);
for (int q = 0; q < Q; ++q) {
ll ans=INF;
for (int i = L[q]; i <=R[q] ; ++i)
ans=min(ans,cum2[R[q]][i]+cum[n-1][i]-(L[q]?cum[L[q]-1][i]:0)-H[i]);
C[q]=ans;
}
return C;
}
