This is the hard version of the problem. The differences between the two versions are the constraint on $$$n$$$ and the time limit. You can make hacks only if both versions of the problem are solved.

You are given a tree with $$$n$$$ vertices rooted at vertex $$$1$$$.

For some permutation$$$^\dagger$$$ $$$a$$$ of length $$$n$$$, let $$$f(a)$$$ be the number of pairs of vertices $$$(u, v)$$$ such that $$$a_u \lt a_{\operatorname{lca}(u, v)} \lt a_v$$$. Here, $$$\operatorname{lca}(u,v)$$$ denotes the lowest common ancestor of vertices $$$u$$$ and $$$v$$$.

Find the maximum possible value of $$$f(a)$$$ over all permutations $$$a$$$ of length $$$n$$$.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$).

The second line contains $$$n - 1$$$ integers $$$p_2,p_3,\ldots,p_n$$$ ($$$1 \le p_i \lt i$$$) indicating that there is an edge between vertices $$$i$$$ and $$$p_i$$$.

Output

Output the maximum value of $$$f(a)$$$.

Note

The tree in the first test:

$\text{[math]}$

One possible optimal permutation $$$a$$$ is $$$[2, 1, 4, 5, 3]$$$ with $$$4$$$ suitable pairs of vertices:

$$$(2, 3)$$$, since $$$\operatorname{lca}(2, 3) = 1$$$ and $$$1 \lt 2 \lt 4$$$,
$$$(2, 4)$$$, since $$$\operatorname{lca}(2, 4) = 1$$$ and $$$1 \lt 2 \lt 5$$$,
$$$(2, 5)$$$, since $$$\operatorname{lca}(2, 5) = 1$$$ and $$$1 \lt 2 \lt 3$$$,
$$$(5, 4)$$$, since $$$\operatorname{lca}(5, 4) = 3$$$ and $$$3 \lt 4 \lt 5$$$.

The tree in the third test:

$\text{[math]}$

The tree in the fourth test:

$\text{[math]}$

✓	#	Name		✎	Rating↕	Solved↕
	2203B	Beautiful Numbers bitmasks dp fft greedy math			1000	16.2k
	1856E2	PermuTree (hard version) bitmasks dfs and similar dp fft greedy implementation math trees			2700	1.8k

Problemset