//#define _GLIBCXX_DEBUG #include<bits/stdc++.h> using namespace std; using ll = long long; using vl = vector<ll>; using vvl = vector<vl>; using vi = vector<int>; using vvi = vector<vector<int>>; typedef pair<ll, ll> P; using vs = vector<string>; using vvs = vector<vs>; using vp = vector<P>; using vvp = vector<vp>; using vb = vector<bool>; using vvb = vector<vb>; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define all(a) (a).begin(), (a).end() #define lb(v, k) (lower_bound(all(v), (k)) - v.begin()) #define ub(v, k) (upper_bound(all(v), (k)) - v.begin()) #define fi first #define se second #define pb push_back #define double long double template <typename T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return true; } return false; } template <typename T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return true; } return false; } ll mod = 998244353; ll inf = 999999999999999999LL; struct union_find{ int n; vl root; vl siz; vvl S; ll ans = 0; void init(int N){ n = N; root.assign(N, -1); siz.assign(N, 1); S.assign(N, vl(2)); } vl st; int leader(int p){ while(root[p] != -1){ st.pb(p); p = root[p]; } for(auto x : st){ root[x] = p; } st.clear(); return p; } bool same(int p, int q){ return (leader(p) == leader(q)); } int merge(int p, int q){ p = leader(p), q = leader(q); if(p != q){ if(siz[p] < siz[q]){ swap(p, q); } S[p][0] += S[q][0]; siz[p] += siz[q]; root[q] = p; } return p; } }; vi root; vl W; ll N = 0; ll ans = 0; vl sm1, sm2; void init(std::vector<int> PP, std::vector<int> WW){ N = PP.size(); root.assign(N, 0); W.assign(N, 0); rep(i, N){ root[i] = PP[i]; W[i] = WW[i]; } vvi X(1000001); rep(i, N){ X[W[i]].pb(i); } vvi G(N); rep(i, N){ if(root[i] != -1){ G[root[i]].pb(i); G[i].pb(root[i]); } } vl now(N); vl leaf(N); union_find D; D.init(N);// leafcnt last vector<ll> que(N + 1); for(int t = 1000000;t >= 0;t--){ for(auto p : X[t]){ now[p] = 1; D.S[p][0] = 1; D.S[p][1] = t; leaf[p] = 1; for(auto q : G[p]){ if(now[q] == 1){ int a, b; a = p, b = q; if(root[a] == b){ swap(a, b); } int c, d; c = D.leader(a), d = D.leader(b); ans += D.S[c][0] * (D.S[c][1] - t); ans += D.S[d][0] * (D.S[d][1] - t); que[D.S[c][0]] += D.S[c][1] - t; que[D.S[d][0]] += D.S[d][1] - t; D.S[c][0] -= leaf[a]; leaf[a] = 0; int r = D.merge(c, d); D.S[r][1] = t; //cout << p << ' ' << q << ' ' << D.S[r][0] << ' ' << D.S[r][1] << endl; } } } } int p = D.leader(0); ans += D.S[p][0] * (D.S[p][1]); que[D.S[p][0]] += D.S[p][1]; sm1.assign(N + 1, 0);//kl sum sm2.assign(N + 1, 0);//R sum sm1[N] = N * que[N]; sm2[N] = que[N]; for(int i = N - 1;i >= 0;i--){ sm1[i] = i * que[i]; sm1[i] += sm1[i + 1]; sm2[i] = que[i]; sm2[i] += que[i + 1]; } return ; } long long query(int L, int R){ ll p = R / L; p++; chmin(p, N); return sm1[p] * L - sm2[p] * R + ans * L; }