//#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;
}
