#include "meetings.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
long long v[5005];
long long dp[5005][5005];
long long maxim[5005][5005];
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
int n=H.size();
for(int i=1;i<=n;i++)
{
maxim[i][i]=i;
v[i]=H[i-1];
dp[i][i]=v[i];
}
for(int dist=2;dist<=n;dist++)
{
for(long long st=1;st+dist-1<=n;st++)
{
long long dr=st+dist-1;
if(v[maxim[st][dr-1]]>=v[dr])
{
maxim[st][dr]=maxim[st][dr-1];
}
else
{
maxim[st][dr]=dr;
}
long long mij=maxim[st][dr];
dp[st][dr]=min(dp[st][mij-1]+(dr-mij+1)*v[mij],dp[mij+1][dr]+(mij-st+1)*v[mij]);
}
}
vector<long long >rez;
for(int i=0;i<Q;i++)
{
rez.push_back(dp[L[i]+1][R[i]+1]);
}
return rez;
}
