#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
pair<int, int> st[1<<21];
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int n=H.size();
vector<ll> ans(L.size(), 1e18);
vector<array<int, 2>> ct(n, {-1, -1});
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++) {
vector<vector<int>> qu(n);
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);
vector<ll> pl(n);
vector<tuple<ll, ll, int, int>> sc(n);
auto getv = [&](tuple<ll, ll, int, int> t, int x) {
auto [a, b, l, r]=t;
return a*x+b;
};
vector<deque<int>> nl(n);
auto cal = [&](int u, int l) {
auto calc = [&](int rb) {
int s=0, e=nl[u].size()-1;
while (s<e) {
int m=(s+e)/2;
if (get<3>(sc[nl[u][m]])<rb) s=m+1;
else e=m;
}
return getv(sc[nl[u][s]], rb)+pl[u];
};
for (int i:qu[u]) ans[i]=min(ans[i], calc(R[i])-1ll*H[u]*(L[i]-l));
};
function<void(int)> dfs = [&](int u) {
if (u==-1) return ;
auto [l, r]=ct[u];
dfs(l);
dfs(r);
int lb=u;
if (l!=-1) swap(nl[l], nl[u]), pl[u]=pl[l], lb=get<2>(sc[nl[u][0]]);
auto &ins = sc[u];
ins={H[u], (nl[u].size()?getv(sc[nl[u].back()], u-1):0)+H[u]-1ll*u*H[u], u, u};
while (nl[u].size()&&get<0>(sc[nl[u].back()])==H[u]) get<2>(ins)=get<2>(sc[nl[u].back()]), nl[u].pop_back();
if (r==-1) {
nl[u].emplace_back(u);
for (int i:qu[u]) ans[i]=min(ans[i], 1ll*(R[i]-L[i]+1)*H[u]);
return ;
}
pl[r]+=1ll*(u-lb+1)*H[u];
swap(nl[r], nl[u]);
swap(pl[r], pl[u]);
cal(u, lb);
swap(nl[r], nl[u]);
swap(pl[r], pl[u]);
while (nl[r].size()) {
if (getv(sc[nl[r][0]], get<3>(sc[nl[r][0]]))+pl[r]>=getv(ins, get<3>(sc[nl[r][0]]))+pl[u]) get<3>(ins)=get<3>(sc[nl[r][0]]), nl[r].pop_front();
else if (getv(sc[nl[r][0]], get<2>(sc[nl[r][0]]))+pl[r]<getv(ins, get<2>(sc[nl[r][0]]))+pl[u]) break;
else {
int s=get<2>(sc[nl[r][0]]), e=get<3>(sc[nl[r][0]]);
while (s<e) {
int m=(s+e+1)/2;
if (getv(sc[nl[r][0]], m)+pl[r]>=getv(ins, m)+pl[u]) s=m;
else e=m-1;
}
get<2>(sc[nl[r][0]])=s+1;
get<3>(ins)=s;
break;
}
}
nl[u].emplace_back(u);
if (nl[u].size()>=nl[r].size()) for (auto &i:nl[r]) get<1>(sc[i])+=pl[r]-pl[u], nl[u].emplace_back(i);
else {
reverse(nl[u].begin(), nl[u].end());
for (auto &i:nl[u]) get<1>(sc[i])+=pl[u]-pl[r], nl[r].emplace_front(i);
swap(nl[u], nl[r]);
pl[u]=pl[r];
}
};
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;
}
