#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second

int n, q;
ll pref[5001][5001], suf[5001][5001], sum[5001];
vector <pair <int, ll> > v;

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
	n = H.size();
	q = L.size();
	vector <ll> c(q);
	for (int i = 0; i < n; i++) {
		sum[i] += H[i];
		ll mx = H[i];
		v.clear();
		v.push_back({mx, i});
		for (int j = i - 1; j >= 0; j--) {
			if (H[j] >= mx) {
				mx = H[j];
				v.push_back({mx, j});
			}
			sum[i] += mx;
		}
		pref[i][0] = mx;
		if (v.back().ss == 0) {
			v.pop_back();
			mx = v.back().ff;
		}
		for (int j = 1; j < i; j++) {
			pref[i][j] = pref[i][j - 1] + mx;
			if (j == v.back().ss) {
				v.pop_back();
				mx = v.back().ff;
			}
		}
		for (int j = i + 1; j < n; j++) {
			if (H[j] >= mx) {
				mx = H[j];
				v.push_back({mx, j});
			}
			sum[i] += mx;	
		}
		suf[i][n - 1] = mx;
		if (v.back().ss == n - 1) {
			v.pop_back();
			mx = v.back().ff;
		}
		for (int j = n - 2; j > i; j--) {
			suf[i][j] = suf[i][j + 1] + mx;
			if (j == v.back().ss) {
				v.pop_back();
				mx = v.back().ff;
			}
		}
	}
	for (int i = 0; i < q; i++) {
		ll mn = (ll)1e18 + 7;
		for (int j = L[i]; j <= R[i]; j++) {
			ll x = 0;
			if (L[i] - 1 >= 0) {
				x += pref[j][L[i] - 1];
			}
			if (R[i] + 1 < n) {
				x += suf[j][R[i] + 1];
			}
			// cout <<  x << " ";
			mn = min(mn, sum[j] - x);
		}
		c[i] = mn;
	}
	return c;
}