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 < i$).

In the very beginning, Pak Chanek must write one integer number on each card. He does this by choosing any permutation $a$ of $[1, 2, \dots, n]$. 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):

Choose a card $x$ such that no other cards are hanging onto it.

Append the number written on card $x$ to the end of $s$.

If $x \neq 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$.

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$^\dagger$ of $s$ at the end if Pak Chanek does all the steps optimally?

$^\dagger$ 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, $[3,1]$ is a subsequence of $[3,2,1]$, $[4,3,1]$ and $[3,1]$, but not $[1,3,3,7]$ and $[3,10,4]$.


-----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 < 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.


-----Examples-----

Input
6
1 2 1 4 2
Output
4
Input
2
1
Output
2


-----Note-----

The following is the structure of the cards in the first example.

Pak Chanek can choose the permutation $a = [1, 5, 4, 3, 2, 6]$.

Let $w_i$ be the number written on card $i$. Initially, $w_i = a_i$. Pak Chanek can do the following operations in order:

Select card $5$. Append $w_5 = 2$ to the end of $s$. As $w_4 > w_5$, the value of $w_4$ becomes $2$. Remove card $5$. After this operation, $s = [2]$.

Select card $6$. Append $w_6 = 6$ to the end of $s$. As $w_2 \leq w_6$, the value of $w_2$ is left unchanged. Remove card $6$. After this operation, $s = [2, 6]$.

Select card $4$. Append $w_4 = 2$ to the end of $s$. As $w_1 \leq w_4$, the value of $w_1$ is left unchanged. Remove card $4$. After this operation, $s = [2, 6, 2]$.

Select card $3$. Append $w_3 = 4$ to the end of $s$. As $w_2 > w_3$, the value of $w_2$ becomes $4$. Remove card $3$. After this operation, $s = [2, 6, 2, 4]$.

Select card $2$. Append $w_2 = 4$ to the end of $s$. As $w_1 \leq w_2$, the value of $w_1$ is left unchanged. Remove card $2$. After this operation, $s = [2, 6, 2, 4, 4]$.

Select card $1$. Append $w_1 = 1$ to the end of $s$. Remove card $1$. After this operation, $s = [2, 6, 2, 4, 4, 1]$.

One of the longest non-decreasing subsequences of $s = [2, 6, 2, 4, 4, 1]$ is $[2, 2, 4, 4]$. Thus, the length of the longest non-decreasing subsequence of $s$ is $4$. It can be proven that this is indeed the maximum possible length.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph traversal

Constructive algorithms

Greedy algorithms

Tree algorithms

Dynamic programming

Data structures


Solutions:
n = int(input())
p = [-1] + [x - 1 for x in list(map(int, input().split()))]
(h, dp) = ([1] * n, [0] * n)
for i in range(n - 1, -1, -1):
	dp[i] = max(dp[i], h[i])
	if i:
		dp[p[i]] += dp[i]
		h[p[i]] = max(h[p[i]], h[i] + 1)
print(dp[0])


n = int(input())
a = [-1] + [int(o) - 1 for o in input().split()]
f = [0] * n
dp = [0] * n
for i in range(n - 1, 0, -1):
	f[a[i]] = max(f[i] + 1, f[a[i]])
for i in range(n - 1, 0, -1):
	dp[i] = max(dp[i], f[i] + 1)
	dp[a[i]] += dp[i]
print(max(dp[0], f[0] + 1))


import sys, threading
from collections import defaultdict

def main():

	def dfs(node):
		d = 1
		childs_sum = 0
		for adj in tree[node]:
			(child_depth, childs_val) = dfs(adj)
			d = max(d, 1 + child_depth)
			childs_sum += childs_val
		return (d, max(childs_sum, d))
	n = int(input())
	pars = list(map(int, input().split()))
	tree = defaultdict(list)
	for i in range(n - 1):
		v = pars[i]
		tree[v].append(i + 2)
	res = dfs(1)
	print(max(*res))
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


from collections import defaultdict
import threading
import sys

def ri():
	return int(input())

def rs():
	return input()

def rl():
	return list(map(int, input().split()))

def rls():
	return list(input().split())
threading.stack_size(10 ** 8)
sys.setrecursionlimit(10 ** 6)

def main():
	n = ri()
	p = rl()
	g = defaultdict(list)
	i = 2
	for par in p:
		g[par].append(i)
		i += 1

	def rec(cn):
		l = 1
		cs = 0
		for nn in g[cn]:
			(cl, ccs) = rec(nn)
			l = max(l, cl + 1)
			cs += ccs
		return (l, max(cs, l))
	res = rec(1)
	print(max(*res))
	pass
threading.Thread(target=main).start()


import sys

def read():
	return [int(x) for x in sys.stdin.readline().split(' ')]
[n] = read()
P = read()
deg = n * [0]
for i in range(len(P)):
	P[i] -= 1
	deg[P[i]] += 1
P = [0] + P
Q = []
for i in range(n):
	if deg[i] == 0:
		Q.append(i)
M = n * [0]
S = n * [0]
while len(Q) > 0:
	i = Q.pop()
	M[i] += 1
	if i == 0:
		continue
	S[P[i]] += max(M[i], S[i])
	M[P[i]] = max(M[P[i]], M[i])
	deg[P[i]] -= 1
	if deg[P[i]] == 0:
		Q.append(P[i])
print(max(M[0], S[0]))