포렌식

위 표는 배열 $A$의 내용이고, 윗줄은 인덱스이다. 이 배열에는 단방향 연결 리스트의 포인터가 들어 있으며, 여기서 포인터는 그냥 정수 값이다. 첫 번째 노드의 포인터는 $A[0]$에 들어 있다. 즉 $A[0]$의 값이 두 번째 노드의 위치이다. 두 번째 노드의 포인터는 $A[A[0]]$에, 세 번째 노드의 포인터는 $A[A[A[0]]]$에 들어 있고, 이런 식으로 이어진다. 포인터 값이 $-1$이면 연결 리스트의 끝이다. 위 예에서 $A[0]$의 값은 2이므로 두 번째 포인터는 $A[2]$에 있다. $A[2]$의 값은 4이므로 세 번째 포인터는 $A[4]$에 있다. $A[4]$의 값은 $-1$이므로 뒤에 오는 노드가 없다. 포인터가 이어지는 순서는 다음과 같고, 이 연결 리스트의 노드는 3개이다.

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

당신은 이런 배열의 값을 넘겨받았고, 그중 한 칸이 다른 값으로 바뀌었다는 이야기도 함께 들었다. 어느 칸인지도, 새로 들어간 값이 무엇인지도 알지 못한다. 새 값이 원래 값과 같아서 배열이 그대로일 수도 있다. 포렌식 전문가인 당신은 원래 배열을 되살리려 한다. 그래서 한 칸만 고쳐서, 고친 배열이 나타내는 연결 리스트의 노드 수를 가장 크게 만들려고 한다. 위 예를 보자.

• $A[4]$를 6으로 고치면 노드가 4개인 연결 리스트가 된다.
• $A[0]$을 7로 고치면 노드가 4개인 연결 리스트가 된다.
• $A[0]$을 9로 고치면 연결 리스트가 성립하지 않는다.
• $A[2]$를 7로 고치면 노드가 5개인 연결 리스트가 된다.

한 칸을 고치는 모든 방법과 아무 칸도 고치지 않는 경우를 통틀어, 노드 5개짜리가 가장 크다. 따라서 $A[2]$의 원래 값이 7이었을 가능성이 높다. 이렇게 되살릴 수 있는 연결 리스트의 최대 노드 수를 구하는 프로그램을 작성하시오.

첫째 줄에 배열의 크기 $N$이 주어진다. 둘째 줄에 배열의 원소 $N$개가 $A[0]$부터 차례대로 공백으로 구분되어 주어진다. 각 원소는 $-1$ 이상 $N$ 미만의 정수이다.

되살린 연결 리스트 가운데 노드 수가 가장 많은 것의 노드 수를 출력한다.