Maximum Height after Left-Child Right-Sibling Conversion

A multiway tree with N nodes numbered from 1 to N (with node 1 as the root) is given. For each node, its parent has a smaller number than itself. Such a tree can be converted to a binary tree using the left-child right-sibling representation. In this process, for every node, you can choose any child as its left child, and then arrange the remaining children arbitrarily as a chain via the right child pointers.

Under the assumption that the children of every node are unordered, the binary tree resulting from the conversion is not unique. Your task is to compute the maximum possible height (i.e. the maximum number of edges in a path from the root to a leaf) among all possible binary trees obtained by such a conversion. (Note: a tree with only the root node has height 0.)

Conversion Explanation: Suppose a node u has children. In the conversion you may order these children arbitrarily. For example, if you let the children of u be v₁, v₂, ..., v_m in some order, then you set u.left = v₁ and for 1 ≤ i < m, set v_i.right = v_i+1. Besides this horizontal chain (which contributes m edges), you also have the option at some node in the chain to follow its left child pointer down into its subtree. Thus, with an optimal ordering, the maximum height obtainable from a node u is given by

$$F(u)=\text{(number of children of }u) + \max_{v \in \text{children of }u} F(v) $$

with F(u)=0 for a leaf node. The answer to the problem is F(root).

inputFormat

The first line contains a single integer N (1 ≤ N ≤ 10⁵) representing the number of nodes in the tree.
The following line contains N - 1 integers. The i-th integer (for i from 2 to N) represents the parent of node i. It is guaranteed that for every node i > 1, its parent is less than i.

outputFormat

Output a single integer, the maximum possible height (i.e. the maximum number of edges) of the binary tree obtained by an optimal left-child right-sibling conversion.

sample

1

0