시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB197763.636%

문제

명찬은 최근에 게임 하나를 시작했다. 리버스 엔지니어링의 고수인 명찬은 게임을 뜯어 본 결과 이 게임에서 제공하는 던전 탐사 컨텐츠가 아래와 같은 구성을 지니고 있다는 것을 알아냈다.

  • 던전은 총 $N(2 \le N \le 2 \cdot 10^5)$개의 방으로 구성되어 있다.
  • $i$번째 방을 클리어하면 $a_i( 1 \le a_i \le N, a_i \neq i)$ 번 방으로 이동하게 된다.
  • 플레이어는 $N$개의 방 중 하나의 방을 골라 해당 방에서 탐사를 시작할 수 있다.
  • 플레이어는 던전 탐사의 결과로 방문한 방의 개수에 비례한 보상을 받게 된다. 같은 방에 여러 번 방문하여도 방문한 방의 개수는 하나로 생각한다.

명찬은 게임에서 최대의 이익을 보기 위해 게임을 해킹한 결과, $i$번째 방을 클리어한 후 이동하게 되는 다음 방 $a_i$를 마음대로 바꿀 수 있게 됐다. 하지만 너무 많은 것을 바꾸면 운영진한테 걸릴 수 있으므로, 최대 하나의 방에 대해서만 $a_i$ 값을 바꾸려고 한다.

이 때, 명찬이 방문 가능한 방의 최대 개수를 출력하여라.

입력

첫 줄에 방의 개수 $N$이 주어진다($2 \le N \le 2 \cdot 10^5 $).

둘째 줄에 각 방을 클리어한 후 이동하게 되는 방의 번호 $a_1, a_2, \dots, a_N$이 순서대로 공백으로 구분되어 주어진다($1 \le a_i \le N$).

출력

첫째 줄에 명찬이 방문 가능한 방의 최대 개수를 출력한다.

예제 입력 1

4
2 1 4 3

예제 출력 1

4

 $a_1$을 3으로 바꾼 후 2번 방에서부터 시작하면 4개의 방을 모두 방문할 수 있다.

예제 입력 2

6
2 3 4 2 4 4

예제 출력 2

5

$a_1$을 $6$으로 바꾼 후 $1$번 방에서부터 시작하면 $1, 6, 4, 2, 3$의 다섯개 방을 방문할 수 있다. 어떻게 해도 주어진 조건 하에서 $5$개보다 많은 방을 방문할 수 있는 방법은 없다.

출처