G. Gastronomic Event
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

SWERC organizers want to hold a gastronomic event.

The location of the event is a building with $$$n$$$ rooms connected by $$$n-1$$$ corridors (each corridor connects two rooms) so that it is possible to go from any room to any other room.

In each room you have to set up the tasting of a typical Italian dish. You can choose from $$$n$$$ typical Italian dishes rated from $$$1$$$ to $$$n$$$ depending on how good they are ($$$n$$$ is the best possible rating). The $$$n$$$ dishes have distinct ratings.

You want to assign the $$$n$$$ dishes to the $$$n$$$ rooms so that the number of pleasing tours is maximal. A pleasing tour is a nonempty sequence of rooms so that:

  • Each room in the sequence is connected to the next one in the sequence by a corridor.
  • The ratings of the dishes in the rooms (in the order given by the sequence) are increasing.
If you assign the $$$n$$$ dishes optimally, what is the maximum number of pleasing tours?
Input

The first line contains an integer $$$n$$$ ($$$2\le n\le 1\,000\,000$$$) — the number of rooms.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \cdots , p_n$$$ ($$$1 \leq p_i < i$$$). Each $$$p_i$$$ indicates that there is a corridor between room $$$i$$$ and room $$$p_i$$$. It is guaranteed that the building has the property that it is possible to go from any room to any other room.

Output

Print the maximum number of pleasing tours.

Examples
Input
5
1 2 2 2
Output
13
Input
10
1 2 3 4 3 2 7 8 7
Output
47
Note

In the first sample, it is optimal to place the dish with rating $$$1$$$ in room $$$1$$$, the dish with rating $$$2$$$ in room $$$3$$$, the dish with rating $$$3$$$ in room $$$2$$$, the dish with rating $$$4$$$ in room $$$5$$$ and the dish with rating $$$5$$$ in room $$$4$$$.

All the $$$13$$$ possible pleasing tours are: $$$(1)$$$, $$$(2)$$$, $$$(3)$$$, $$$(4)$$$, $$$(5)$$$, $$$(1,2)$$$, $$$(3,2)$$$, $$$(2,4)$$$, $$$(2,5)$$$, $$$(1,2,4)$$$, $$$(1,2,5)$$$, $$$(3,2,4)$$$, $$$(3,2,5)$$$.

There are also other ways to assign the dishes to the rooms so that there are $$$13$$$ pleasing tours.