시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 114 26 22 21.359%

문제

초등학교에서도 중학교에서도 고등학교에서도 대학교에서도 소풍에서도 엠티에서도 낮이나 밤이나 봄이나 여름이나 가을이나 겨울이나 실내에서도 실외에서도 손쉽게 즐길 수 있는 마.피.아.게.임!

마피아 게임의 룰은 다음과 같다. 참가자는 몇 명은 "마피아"가 되고, 마피아를 제외한 나머지는 "시민"이 된다. 마피아끼리는 누가 마피아인지 알지만 시민은 누가 마피아인지 모른다. 그리고 시민들은 누가 마피아인지 게임을 진행하면서 알아내면 된다.

게임이 진행되면서 현재 N명의 살아남은 참가자들이 있고, 그들은 누가 마피아인지 밝혀내야 한다. 시민들은 짐작을 통해 마피아를 지목하고 마피아로 지목된 사람은 아무것도 모르는 척, 마피아가 아닌 척을 한다.

누가 마피아인지 모를 때, 이 참가자들 중에 마피아가 최대한 몇 명이나 있을 수 있을까? 

입력

첫째 줄에는 정수 N(2 < N < 500000)이 주어진다. N은 참가자의 수이다. 참가자들은 1에서 N까지의 수를 등에 붙인다.

이후 N개의 줄이 주어지고 K번째 줄은 등번호가 K번인 참가자에 의해 지목당한 등번호이다. (자기자신은 지목할 수 없다.)

출력

이 게임에서 가능한 마피아의 최대 인원을 출력한다.

예제 입력

3
2
1
1

예제 출력

2

예제 입력 2

3
2
3
1

예제 출력 2

1

예제 입력 3

7
3
3
4
5
6
4
4

예제 출력 3

4

힌트

첫번째 예제에서 마피아일 것이라고 생각되는 참가자는 2번과 3번이다.

두번째 예제에서는 어느 누구나 마피아로 생각될 수 있다.

마피아끼리는 서로 누군지 아는 상황이기 때문에 서로 지목을 안 하려고 할 것이다.