#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define int long long
const int inf = 1e18+10;
const int maxn = 8e5+10;
int n, a[maxn];
pair<int,int> tr[maxn];
map<int,int> dp[maxn];
void build(int no, int l, int r) {
if(l == r) {
tr[no] = mp(a[l],l);
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
tr[no] = max(tr[lc],tr[rc]);
}
pair<int,int> querymax(int no, int l, int r, int L, int R) {
if(l > R || r < L) return mp(-inf,0);
if(l >= L && r <= R) return tr[no];
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
return max(querymax(lc,l,mid,L,r),querymax(rc,mid+1,r,L,R));
}
int sol(int l, int r) {
if(dp[l].count(r)) return dp[l][r];
if(l > r) return dp[l][r] = 0;
int i = querymax(1,1,n,l,r).sc;
return dp[l][r] = min({(r-l+1)*a[i],sol(l,i-1)+(r-i+1)*a[i],sol(i+1,r)+(r-i+1)*a[i]});
}
vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L, vector<int32_t> R) {
// int Q = L.size();
// std::vector<long long> C(Q);
// for (int j = 0; j < Q; ++j) {
// C[j] = H[L[j]];
// }
// return C;
n = H.size();
for(int i = 1; i <= n; i++) {
a[i] = H[i-1];
}
vector<int> ans;
for(int i = 0; i < L.size(); i++) {
ans.pb(sol(L[i]+1,R[i]+1));
}
return ans;
}
