## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Hanging Hearts Codeforces Solution

E. Hanging Hearts
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pak Chanek has $n$ blank heart-shaped cards. Card $1$ is attached directly to the wall while each of the other cards is hanging onto exactly one other card by a piece of string. Specifically, card $i$ ($i>1$) is hanging onto card ${p}_{i}$ (${p}_{i}).

In the very beginning, Pak Chanek must write one integer number on each card. He does this by choosing any permutation $a$ of $\left[1,2,\dots ,n\right]$. Then, the number written on card $i$ is ${a}_{i}$.

After that, Pak Chanek must do the following operation $n$ times while maintaining a sequence $s$ (which is initially empty):

1. Choose a card $x$ such that no other cards are hanging onto it.
2. Append the number written on card $x$ to the end of $s$.
3. If $x\ne 1$ and the number on card ${p}_{x}$ is larger than the number on card $x$, replace the number on card ${p}_{x}$ with the number on card $x$.
4. Remove card $x$.

After that, Pak Chanek will have a sequence $s$ with $n$ elements. What is the maximum length of the longest non-decreasing subsequence${}^{†}$ of $s$ at the end if Pak Chanek does all the steps optimally?

${}^{†}$ A sequence $b$ is a subsequence of a sequence $c$ if $b$ can be obtained from $c$ by deletion of several (possibly, zero or all) elements. For example, $\left[3,1\right]$ is a subsequence of $\left[3,2,1\right]$$\left[4,3,1\right]$ and $\left[3,1\right]$, but not $\left[1,3,3,7\right]$ and $\left[3,10,4\right]$.

Input

The first line contains a single integer $n$ ($2\le n\le {10}^{5}$) — the number of heart-shaped cards.

The second line contains $n-1$ integers ${p}_{2},{p}_{3},\dots ,{p}_{n}$ ($1\le {p}_{i}) describing which card that each card hangs onto.

Output

Print a single integer — the maximum length of the longest non-decreasing subsequence of $s$ at the end if Pak Chanek does all the steps optimally.