#include <bits/stdc++.h>
using namespace std ;
#define pb push_back
typedef long long ll ;
typedef vector < int > vi ;
typedef vector < ll > vll ;
const ll inf = 1e18 ;
#include "meetings.h"
ll n , q ;
ll h [5009] ;
ll cost [5009][5009] , sum [5009][5009] ;
ll calc ( ll id , ll l , ll r ) {
return ( l <= r ? sum [id][r] - ( l ? sum [id][l-1] : 0 ) : 0 ) ;
}
vll minimum_costs ( vi H , vi L , vi R) {
n = H .size () , q = L .size () ;
for ( ll i = 0 ; i < n ; i ++ ) {
h [i] = H [i] ;
}
for ( ll i = 0 ; i < n ; i ++ ) {
ll mx = 0 ;
for ( ll j = i ; j < n ; j ++ ) {
mx = max ( mx , h [j] ) ;
cost [i][j] = mx ;
}
mx = 0 ;
for ( ll j = i ; j >= 0 ; j -- ) {
mx = max ( mx , h [j] ) ;
cost [i][j] = mx ;
}
ll crnt = 0 ;
for ( ll j = 0 ; j < n ; j ++ ) {
crnt += cost [i][j] ;
sum [i][j] = crnt ;
}
}
vll ans ;
for ( int i = 0 ; i < q ; i ++ ) {
ll l = L [i] , r = R [i] , mn = inf ;
for ( ll j = l ; j <= r ; j ++ ) {
mn = min ( mn , calc ( j , l , r ) ) ;
}
ans .pb ( mn ) ;
}
return ans ;
}
