I. Sum of Path Lengths
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given an undirected tree with $$$n$$$ vertices. Find the sum of lengths of all simple paths in it.

The length of a simple path between vertices $$$u$$$ and $$$v$$$ is the minimum number of edges that need to be traversed to go from $$$u$$$ to $$$v$$$.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 300\,000$$$).

The next line contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \lt i$$$). They mean that there is an edge in the tree between $$$2$$$ and $$$p_2$$$, an edge between $$$3$$$ and $$$p_3$$$, ..., an edge between $$$n$$$ and $$$p_n$$$. It is guaranteed that the given edges form a tree.

Output

Output a single integer: the sum over all $$$(u, v)$$$, where $$$1 \le u \le v \le n$$$, of the lengths of simple paths between $$$u$$$ and $$$v$$$.

Example
Input
5
1 1 3 1
Output
18