#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
const ll inf = 1e18;
ll lc[MAXN][MAXN], rc[MAXN][MAXN], ls[MAXN][MAXN], rs[MAXN][MAXN];
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
int nums = H.size();
vector<pair<int, ll>> vec;
vec.push_back({-1, inf});
for (int i = 0; i < nums; i++){
while (vec.back().second <= H[i]) vec.pop_back();
vec.push_back({i, H[i]});
int curr = 1;
for (int j = 0; j < i; j++){
while (vec[curr].first < j) curr++;
lc[i][j] = max(lc[i - 1][j], vec[curr].second);
}
lc[i][i] = ls[i][i] = H[i];
for (int j = i - 1; j >= 0; j--) ls[i][j] = ls[i][j + 1] + lc[i][j];
}
vec.clear();
vec.push_back({nums, inf});
for (int i = nums - 1; i >= 0; i--){
while (vec.back().second <= H[i]) vec.pop_back();
vec.push_back({i, H[i]});
int curr = 1;
for (int j = nums - 1; j > i; j--){
while (vec[curr].first > j) curr++;
rc[i][j] = max(rc[i + 1][j], vec[curr].second);
}
rc[i][i] = rs[i][i] = H[i];
for (int j = i + 1; j < nums; j++) rs[i][j] = rs[i][j - 1] + rc[i][j];
}
int queries = L.size();
vector<ll> ans(queries);
for (int q = 0; q < queries; q++){
int l = L[q], r = R[q];
ll res = inf;
for (int m = l; m <= r; m++) res = min(res, ls[m][l] + rs[m][r] - H[m]);
ans[q] = res;
}
return ans;
}
