#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>; using ti = array<ll,3>;
const ll INF = 1e18;
vector<ll> gseg(vector<ll> H) { //get segment values
ll N = H.size();
ll xl = 0; ll xr = N-1;
if (H.size()==0) {
return vector<ll>(0);
}
set<pii> hpmax; //h pair max
for (ll i=0;i<N;i++) {
hpmax.insert((pii){H[i],i});
}
ll T = 0; //# of iteration
vector<ll> v1,v2; //val1/val2 vectors
while (xl<=xr) {
assert(!hpmax.empty());
auto A0 = *(--hpmax.end()); hpmax.erase(--hpmax.end());
ll hmax = A0.first; ll x = A0.second;
assert(x>=0 && x<N);
if (x<xl || xr<x) {
continue; //break loop & restart
}
T++;
ll a = (x-xl); ll b = (xr-x);
if (a<b) {
//recursion call on left
vector<ll> rcall;
for (ll x0=xl;x0<x;x0++) {
rcall.push_back(H[x0]);
}
vector<ll> qryL = gseg(rcall);
if (qryL.size()==0) {
qryL.push_back(0);
}
ll val1 = qryL[0]+hmax*(xr-x+1);
ll val2 = (x-xl+1)*hmax;
v1.push_back(val1);
v2.push_back(val2);
xl = x+1;
} else {
//instead call on right
vector<ll> rcall;
for (ll x0=x;x0<xr;x0++) {
rcall.push_back(H[x0]);
}
vector<ll> qryL = gseg(rcall);
if (qryL.size()==0) {
qryL.push_back(0);
}
ll val1 = qryL[0]+hmax*(x-xl+1);
ll val2 = (xr-x+1)*hmax;
v1.push_back(val1);
v2.push_back(val2);
xr = x-1;
}
}
assert(T==v1.size());
assert(T==v2.size());
vector<ll> ansv;
ansv.push_back(0);
for (ll t=(T-1);t>=0;t--) {
ansv.push_back(min(v1[t],v2[t]+ansv.back()));
}
vector<ll> iansv;
for (ll t=0;t<=T;t++) {
iansv.push_back(ansv[T-t]);
}
return iansv;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
ll N = H.size();
ll Q = L.size();
vector<ll> ans(Q);
for (ll q=0;q<Q;q++) {
vector<ll> Hqry;
for (ll x=L[q];x<=R[q];x++) {
Hqry.push_back(H[x]);
}
ans[q]=gseg(Hqry)[0];
}
return ans;
}
