Forensic

The table above shows the content of an array $A$, with the indices in the top row. The array stores the pointers of a singly linked list, and here a pointer is just an integer value. The pointer of the first node sits in $A[0]$, so the value of $A[0]$ is the location of the second node. The pointer of the second node sits in $A[A[0]]$, the pointer of the third node sits in $A[A[A[0]]]$, and so on. A pointer with value $-1$ is the end of the linked list. In the example above, $A[0]$ is 2, so the second pointer sits in $A[2]$. The value of $A[2]$ is 4, so the third pointer sits in $A[4]$. The value of $A[4]$ is $-1$, so no further node follows. The sequence of pointers is written below, and this linked list has 3 nodes.

$A[0] = 2 \rightarrow A[2] = 4 \rightarrow A[4] = -1$

You received the entries of an array like this, and you were told that one entry was replaced. Neither the position of that entry nor its new value is known. The new value may equal the original one, in which case the array is unchanged. As a forensic expert you want to recover the original array, so you want to modify a single entry and make the modified array represent a linked list with as many nodes as possible. Consider the example above.

• Changing $A[4]$ to 6 gives a linked list of 4 nodes.
• Changing $A[0]$ to 7 gives a linked list of 4 nodes.
• Changing $A[0]$ to 9 gives no valid linked list.
• Changing $A[2]$ to 7 gives a linked list of 5 nodes.

Among all changes to one entry, including changing nothing, the recovered list of 5 nodes is the largest. So the original entry of $A[2]$ was probably 7. Compute the size of the largest linked list that can be recovered this way.

The first line contains $N$, the size of the array. The second line contains the $N$ entries of the array separated by spaces, starting from $A[0]$. Every entry is an integer that is at least $-1$ and less than $N$.

Print the number of nodes in the largest recovered linked list.