#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef local
#define cerr if(false)cerr
#endif
const int MAX_N = 1e6 + 10;
int n, q, arr[MAX_N];
ll solve(ll l, ll r) {
if(r < l) { return 0; }
if(l == r) { return arr[l]; }
int mx = max_element(arr + l, arr + r + 1) - arr;
ll ret = arr[mx] * (r - l + 1);
ll lft = solve(l, mx - 1) + (r - mx + 1) * arr[mx];
ll rght = solve(mx + 1, r) + (mx - l + 1) * arr[mx];
return min({ret, lft, rght});
}
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
vector<ll> ret = {};
int q = l.size();
int n = h.size();
for(int i = 0; i < n; i ++) {
arr[i] = h[i];
}
for(int i = 0; i < q; i ++) {
ret.push_back(solve(l[i], r[i]));
}
return ret;
}
