A company has n employees numbered from 1 to n. Each employee either has no immediate manager or exactly one immediate manager, who is another employee with a different number. An employee A is said to be the superior of another employee B if at least one of the following is true:

  * Employee A is the immediate manager of employee B
  * Employee B has an immediate manager employee C such that employee A is the superior of employee C. 



The company will not have a managerial cycle. That is, there will not exist an employee who is the superior of his/her own immediate manager.

Today the company is going to arrange a party. This involves dividing all n employees into several groups: every employee must belong to exactly one group. Furthermore, within any single group, there must not be two employees A and B such that A is the superior of B.

What is the minimum number of groups that must be formed?

Input

The first line contains integer n (1 ≤ n ≤ 2000) — the number of employees.

The next n lines contain the integers pi (1 ≤ pi ≤ n or pi = -1). Every pi denotes the immediate manager for the i-th employee. If pi is -1, that means that the i-th employee does not have an immediate manager. 

It is guaranteed, that no employee will be the immediate manager of him/herself (pi ≠ i). Also, there will be no managerial cycles.

Output

Print a single integer denoting the minimum number of groups that will be formed in the party.

Examples

Input

5
-1
1
2
1
-1


Output

3

Note

For the first example, three groups are sufficient, for example: 

  * Employee 1 
  * Employees 2 and 4 
  * Employees 3 and 5

Difficulty: EASY
Tags: Tree algorithms

Graph algorithms

Graph traversal

Starter code:

Solutions:
def findDepth(a, i):
	depth = 1
	nextLevel = a[i][:]
	while len(nextLevel) > 0:
		depth += 1
		children = nextLevel[:]
		nextLevel = []
		for child in children:
			nextLevel += a[child]
	return depth
n = int(input())
a = []
for i in range(n):
	a.append([])
roots = []
for i in range(n):
	x = int(input())
	if x > 0:
		a[x - 1].append(i)
	else:
		roots.append(i)
print(max([findDepth(a, i) for i in roots]))


from sys import setrecursionlimit
setrecursionlimit(30000)
maxl = -1

def dfs(v, lvl):
	used[v] = True
	global maxl
	if lvl > maxl:
		maxl = lvl
	for u in ch[v]:
		dfs(u, lvl + 1)
n = int(input())
used = [False] * n
p = [int(input()) - 1 for i in range(n)]
ch = [[] for i in range(n)]
for i in range(n):
	if p[i] != -2:
		ch[p[i]].append(i)
for i in range(n):
	if p[i] == -2:
		dfs(i, 1)
print(maxl)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	n = I()
	p = [I() for _ in range(n)]
	fm = {}
	fm[-1] = 0

	def f(i):
		if i in fm:
			return fm[i]
		t = f(p[i - 1]) + 1
		fm[i] = t
		return t
	r = 0
	for i in range(1, n + 1):
		t = f(i)
		if r < t:
			r = t
	return r
print(main())


n = int(input())
a = []
for i in range(n):
	a.append(int(input()) - 1)
ans = 0
for i in range(len(a)):
	L = 0
	while i > -2:
		i = a[i]
		L += 1
	ans = max(ans, L)
print(ans)


from collections import *

class graph:

	def __init__(self, gdict=None):
		if gdict is None:
			gdict = defaultdict(list)
		(self.gdict, self.edges) = (gdict, [])

	def get_vertices(self):
		return list(self.gdict.keys())

	def add_edge(self, node1, node2):
		self.gdict[node1].append(node2)
		self.edges.append([node1, node2])

	def bfs_util(self, i):
		(queue, self.visit[i], level) = (deque([[i, 1]]), 1, 1)
		while queue:
			(s, level) = queue.popleft()
			for i in self.gdict[s]:
				if self.visit[i] == 0:
					queue.append([i, level + 1])
					self.visit[i] = 1
		return level

	def bfs(self):
		(self.visit, self.cnt) = (defaultdict(int), 0)
		for i in pars:
			if self.visit[i] == 0:
				self.cnt = max(self.bfs_util(i), self.cnt)
		return self.cnt
(n, g, pars) = (int(input()), graph(), [])
for i in range(1, n + 1):
	x = int(input())
	if x == -1:
		pars.append(i)
	else:
		g.add_edge(x, i)
print(g.bfs())


from collections import deque

def bfs(u):
	global n, al, dist, prev, used
	q = deque()
	q.append(u)
	md = 1
	used[u] = True
	while len(q) > 0:
		v = q.popleft()
		for i in al[v]:
			if not used[i]:
				used[i] = True
				dist[i] = dist[v] + 1
				if dist[i] + 1 > md:
					md = dist[i] + 1
				q.append(i)
	return md
n = int(input())
al = [[] for i in range(n)]
dist = [0] * n
prev = [0] * n
used = [False] * n
p = [-1] * n
for i in range(n):
	x = int(input()) - 1
	if x >= 0:
		p[i] = x
		al[x].append(i)
res = 0
a = []
for i in range(n):
	if p[i] == -1:
		a.append(i)
i = 0
while i < len(a):
	if not used[a[i]]:
		res = max(res, bfs(a[i]))
	else:
		i += 1
print(res)


n = int(input())
p = [int(input()) - 1 for i in range(n)]
m = 0
for i in range(len(p)):
	c = 0
	while i != -2:
		c += 1
		i = p[i]
	m = max(c, m)
print(m)


size = int(input())
lis = [-1] * size
for y in range(size):
	lis[y] = int(input()) - 1
r = [0] * size
for x in range(size):
	c = x
	while lis[c] > -1:
		r[x] += 1
		c = lis[c]
print(max(r) + 1)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return map(int, input().split())

def array():
	return [int(i) for i in input().split()]
ind = []

def dfs(adj, s, vis, c):
	global ind
	ind.append(c)
	vis[s] = True
	for i in adj[s]:
		if vis[i] == False:
			dfs(adj, i, vis, c + 1)
adj = defaultdict(list)
n = int(input())
ar = []
for i in range(n):
	a = int(input())
	ar.append(a)
	if a != -1:
		adj[a].append(i + 1)
		adj[i + 1].append(a)
ans = 0
vis = {i: False for i in range(1, n + 1)}
for i in range(1, n + 1):
	if ar[i - 1] == -1 and vis[i] == False:
		dfs(adj, i, vis, 0)
print(max(ind) + 1)


n = int(input())
l = [int(input()) - 1 for i in range(n)]
cc = 0
for i in range(n):
	c = 0
	while i != -2:
		i = l[i]
		c += 1
	cc = max(c, cc)
print(cc)


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
n = int(input())
l = []
for i in range(n):
	l.append(int(input()))
m = 0
for i in range(n):
	c = 0
	while i > -1:
		c += 1
		i = l[i] - 1
	m = max(m, c)
print(m)