J. You Are Given a Tree
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Vlad doesn't like to read. Grisha likes formal statements. Vlad came up with the task. Grisha wrote a statement. As there was no way you can find a story here, they would like you to recall that a tree of size $$$n$$$ is a connected undirected graph with $$$n$$$ vertices and $$$n - 1$$$ edges. You are given a tree of size $$$n$$$. We denote as $$$V$$$ ($$$|V| = n$$$) the set of its vertices. Vertices are numbered with consecutive integers from $$$1$$$ to $$$n$$$.

For any $$$S \subset V$$$, we define its $$$\textit{beauty}$$$ as a size of the smallest set of vertices $$$T$$$ ($$$T \subset V$$$) such that for any two vertices $$$u, v \in S$$$ all vertices on the unique simple path between $$$u$$$ and $$$v$$$ belong to $$$T$$$.

For any $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) we define $$$S(l, r)$$$ as a set of vertices $$$\{l, l + 1, l + 2, ... r - 1, r\}$$$.

Find the sum of the beauties of $$$S(l, r)$$$ for all $$$1 \leq l \leq r \leq n$$$.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \leq n \leq 300\,000$$$), the number of vertices in the tree.

Next $$$n - 1$$$ lines contain the description of the tree. The $$$i$$$-th of these lines (lines are numbered from $$$1$$$) contains a single integer $$$p_i$$$ ($$$1 \leq p_i \leq i$$$) describing an edge between vertices $$$p_i$$$ and $$$i + 1$$$.

Output

Output a single integer — the sum of the beauties of all $$$S(l, r)$$$.

Examples
Input
2
1
Output
4
Input
3
1
1
Output
11
Note

In the second sample, there are six sets.

  1. $$$S = \{1\}, T = \{1\}$$$;
  2. $$$S = \{2\}, T = \{2\}$$$;
  3. $$$S = \{3\}, T = \{3\}$$$;
  4. $$$S = \{1, 2\}, T = \{1, 2\}$$$;
  5. $$$S = \{2, 3\}, T = \{1, 2, 3\}$$$;
  6. $$$S = \{1, 2, 3\}, T = \{1, 2, 3\}$$$.