파일 업로드

고정 자리

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

학생들의 스트레스를 풀어주기 위해 선생님은 교실에 거대한 디스코 볼을 설치하고 학생들에게 춤을 가르치려고 합니다!

선생님은 학생들에게 '셔플'을 가르치기로 결정했습니다. 셔플은 NN ( 1N100,0001 \leq N \leq 100,000 ) 명의 학생들이 어떤 순서로 한 줄로 선 후 계속해서 '셔플'을 하고, 각각의 셔플마다 학생들의 순서를 재배열하는 것입니다. 학생들이 자신들의 위치를 쉽게 찾을 수 있도록, 선생님은 학생들의 줄을 위치별로 1N1 \ldots N까지 표시해둡니다. 따라서 줄의 처음 학생은 위치 1에, 다음 학생은 위치 2에 있게 되며, 이런 식으로 위치 NN까지 이어집니다.

셔플은 NN개의 숫자 a1aNa_1 \ldots a_N으로 설명되며, 위치 ii에 있는 학생은 셔플 동안 위치 aia_i로 이동합니다(따라서, 각 aia_i1N1 \ldots N 범위에 있게 됩니다). 모든 학생은 셔플 동안 새로운 위치로 이동합니다. 불행히도, 모든 aia_i가 서로 다른 것은 아니므로, 여러 학생이 셔플 동안 같은 위치로 이동하려고 시도할 수 있고, 이 후에는 남아있는 모든 셔플 동안 함께 움직이게 됩니다.

선생님은 몇몇 위치에는 얼마나 많은 셔플이 이루어지든 상관없이 항상 학생이 위치함을 알아차렸습니다. 몇 개의 위치가 이런 식으로 항상 소를 포함하는지를 세어서 알려 주세요.

💻 입력

첫 번째 입력 줄에는 학생의 수 NN이 있습니다. 다음 줄에는 NN개의 정수 a1aNa_1 \ldots a_N이 있습니다.

🖨️ 출력

어떤 셔플이 이루어지든 항상 학생을 포함하게 될 위치의 수를 출력해주세요.


💻 예제 입력 1
4
3 2 1 3
🖨️ 예제 출력 1
3

출처: USACO 2017 December Contest, Silver Problem 3. The Bovine Shuffle