#include <bits/stdc++.h>
using namespace std;
#define fo(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define print(x) cout << x << "\n";
# define vint vector<int>
# define vll vector<long long>
ll recur(int l, int r, vint h)
{ // r is non-inclsuive
if (r - l <=1)
{
return h[l];
}
int maxH = -1;
fo(i, l, r)
{
maxH = max(maxH, h[i]);
}
vector<pair<pair<int, int>, ll>> aves;
// stores the left and right, and then the sum of the middle
int leftH = l;
fo(i, l, r)
{
if (h[i] == maxH)
{
ll tmp = recur(leftH, i, h);
aves.push_back({{leftH, i}, tmp});
leftH = i + 1;
}
}
if (leftH != r)
{
ll tmp = recur(leftH, r, h);
aves.push_back({{leftH, r}, tmp});
}
int index=-1;
double minAve = maxH + 1;
fo(i,0,aves.size()){
double maxtmp = 0.0 + aves[i].second / (aves[i].first.second - aves[i].first.first+1);
if(maxtmp < minAve){
minAve=maxtmp;
index=i;
}
}
ll numMax = (r - aves[index].first.second) + (aves[index].first.first-l);
return 1ll * numMax * maxH + aves[index].second;
}
//looking for smallest ave
// h - heights
// l, r - left and right bounds of each meeting
// ll minCosts[750000];
vll minCosts;
vll minimum_costs(vint h, vint l, vint r)
{
int numMeetings = l.size();
minCosts.reserve(numMeetings);
fo(i, 0, numMeetings)
{
minCosts.push_back(recur(l[i], r[i] + 1, h));
}
return minCosts;
}
// int main()
// {
// ios::sync_with_stdio(0);
// cin.tie(0);
// vint h = {2, 4, 3, 5};
// vint l = {0, 1};
// vint r = {2, 3};
// vll tmp = minimum_costs(h, l, r);
// fo(i,0,tmp.size()){
// print(tmp[i]);
// }
// }
