#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
pair<ll, ll> sc[1<<20];
vector<int> ls, le, nxt, cnt;
vector<int> H, L, R;
vector<ll> ans, pl;
vector<vector<int>> qu;
vector<array<int, 2>> ct;
pair<int, int> st[1<<21];
ll getv(int i, int x) {
return sc[i].first*x+sc[i].second;
}
void cal(int u, int l) {
sort(qu[u].begin(), qu[u].end(), [&](int x, int y) { return R[x]<R[y]; });
int st=ls[u];
for (int i:qu[u]) {
while (st<le[u]&&nxt[st]<=R[i]) st=nxt[st];
ans[i]=min(ans[i], getv(st, R[i])+pl[u]-1ll*H[u]*(L[i]-l));
}
}
void dfs(int u) {
if (u==-1) return ;
auto [l, r]=ct[u];
dfs(l);
dfs(r);
if (l!=-1) ls[u]=ls[l], pl[u]=pl[l], cnt[u]+=cnt[l];
sc[u]={H[u], (l!=-1?getv(le[l], u-1)+pl[u]:0)+H[u]-1ll*u*H[u]-pl[u]};
if (r==-1) {
for (int i:qu[u]) ans[i]=min(ans[i], 1ll*(R[i]-L[i]+1)*H[u]);
return ;
}
pl[r]+=1ll*(u-ls[u]+1)*H[u];
swap(ls[r], ls[u]);
swap(le[r], le[u]);
swap(pl[r], pl[u]);
cal(u, ls[r]);
swap(ls[r], ls[u]);
swap(le[r], le[u]);
swap(pl[r], pl[u]);
while (nxt[u]<=le[r]) {
if (getv(nxt[u], nxt[nxt[u]]-1)+pl[r]>=getv(u, nxt[nxt[u]]-1)+pl[u]) nxt[u]=nxt[nxt[u]], cnt[r]--;
else if (getv(nxt[u], nxt[u])+pl[r]<getv(u, nxt[u])+pl[u]) break;
else {
int s=nxt[u], e=nxt[nxt[u]]-1;
while (s<e) {
int m=(s+e+1)/2;
if (getv(nxt[u], m)+pl[r]>=getv(u, m)+pl[u]) s=m;
else e=m-1;
}
if (s+1<nxt[nxt[u]]) {
sc[s+1]=sc[nxt[u]], nxt[s+1]=nxt[nxt[u]];
if (nxt[u]==le[r]) le[r]=s+1;
}
nxt[u]=s+1;
break;
}
}
if (cnt[u]<cnt[r]) {
for (int i=ls[u]; i<=u; i=nxt[i]) sc[i].second+=pl[u]-pl[r];
pl[u]=pl[r];
}
else for (int i=nxt[u]; i<=le[r]; i=nxt[i]) sc[i].second+=pl[r]-pl[u];
if (nxt[u]<=le[r]) le[u]=le[r];
cnt[u]+=cnt[r];
}
vector<ll> minimum_costs(vector<int> hh, vector<int> ll, vector<int> rr) {
int n=hh.size();
H=hh;
L=ll;
R=rr;
ans.resize(L.size(), 1e18);
ct.resize(n, {-1, -1});
qu.resize(n);
pl.resize(n);
ls.resize(n);
le=nxt=cnt=ls;
for (int &i:nxt) i++;
vector<int> pr(n), lc(n, -1), rc(n, -1);
int rt=0;
for (int i=1, lst; i<n; i++) {
lst=i-1;
while (H[lst]<H[i]&&lst!=rt) lst=pr[lst];
if (H[lst]<H[i]) pr[rt]=i, lc[i]=rt, rt=i;
else if (rc[lst]==-1) rc[lst]=i, pr[i]=lst;
else pr[rc[lst]]=i, lc[i]=rc[lst], rc[lst]=i, pr[i]=lst;
}
for (int i=0; i<n; i++) ct[i]={lc[i], rc[i]};
for (int tr=0; tr<2; tr++) {
for (int i=0; i<n; i++) qu[i].clear(), pl[i]=0, ls[i]=i, cnt[i]=1;
le=nxt=ls;
for (int &i:nxt) i++;
memset(st, 0, sizeof(st));
for (int i=0; i<n; i++) st[i+(1<<20)]={H[i], i*(tr?1:-1)};
for (int i=(1<<20)-1; i; i--) st[i]=max(st[i*2], st[i*2+1]);
auto getmx = [&](int l, int r) {
l+=(1<<20);
r+=(1<<20);
pair<int, int> rt(0, 0);
while (l<=r) {
if (l%2) rt=max(rt, st[l]), l++;
if (r%2==0) rt=max(rt, st[r]), r--;
l/=2;
r/=2;
}
return rt.second*(tr?1:-1);
};
for (int i=0; i<L.size(); i++) qu[getmx(L[i], R[i])].emplace_back(i);
dfs(rt);
reverse(H.begin(), H.end());
for (int i=0; i<L.size(); i++) tie(L[i], R[i])=make_pair(n-1-R[i], n-1-L[i]);
rt=n-1-rt;
for (auto &[l, r]:ct) tie(l, r)=make_pair(r==-1?-1:n-1-r, l==-1?-1:n-1-l);
reverse(ct.begin(), ct.end());
}
return ans;
}
