시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 265 59 47 25.967%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3
2
1
1

예제 출력 1

2

예제 입력 2

3
2
3
1

예제 출력 2

1

예제 입력 3

7
3
3
4
5
6
4
4

예제 출력 3

4

힌트

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

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

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

W3sicHJvYmxlbV9pZCI6IjEwNTQyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViOWM4XHVkNTNjXHVjNTQ0IFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjZDA4XHViNGYxXHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjXHViM2M0IFx1YzkxMVx1ZDU1OVx1YWQ1MFx1YzVkMFx1YzExY1x1YjNjNCBcdWFjZTBcdWI0ZjFcdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWNcdWIzYzQgXHViMzAwXHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjXHViM2M0IFx1YzE4Y1x1ZDQ4ZFx1YzVkMFx1YzExY1x1YjNjNCZuYnNwO1x1YzVlMFx1ZDJmMFx1YzVkMFx1YzExY1x1YjNjNCBcdWIwYWVcdWM3NzRcdWIwOTggXHViYzI0XHVjNzc0XHViMDk4IFx1YmQwNFx1Yzc3NFx1YjA5OCBcdWM1ZWNcdWI5ODRcdWM3NzRcdWIwOTggXHVhYzAwXHVjNzQ0XHVjNzc0XHViMDk4IFx1YWNhOFx1YzZiOFx1Yzc3NFx1YjA5OCBcdWMyZTRcdWIwYjRcdWM1ZDBcdWMxMWNcdWIzYzQgXHVjMmU0XHVjNjc4XHVjNWQwXHVjMTFjXHViM2M0IFx1YzE5MFx1YzI3ZFx1YWM4YyBcdWM5OTBcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWI5YzguXHVkNTNjLlx1YzU0NC5cdWFjOGMuXHVjNzg0ITxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWQ1M2NcdWM1NDQgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YjhmMFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWNjMzhcdWFjMDBcdWM3OTBcdWIyOTQgXHViYTg3IFx1YmE4NVx1Yzc0MCAmcXVvdDtcdWI5YzhcdWQ1M2NcdWM1NDQmcXVvdDtcdWFjMDAgXHViNDE4XHVhY2UwLCBcdWI5YzhcdWQ1M2NcdWM1NDRcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YjA5OFx1YmEzOFx1YzljMFx1YjI5NCAmcXVvdDtcdWMyZGNcdWJiZmMmcXVvdDtcdWM3NzQgXHViNDFjXHViMmU0LiZuYnNwO1x1YjljOFx1ZDUzY1x1YzU0NFx1YjA3Y1x1YjlhY1x1YjI5NCBcdWIyMDRcdWFjMDAgXHViOWM4XHVkNTNjXHVjNTQ0XHVjNzc4XHVjOWMwIFx1YzU0Y1x1YzljMFx1YjljYyBcdWMyZGNcdWJiZmNcdWM3NDAgXHViMjA0XHVhYzAwIFx1YjljOFx1ZDUzY1x1YzU0NFx1Yzc3OFx1YzljMCBcdWJhYThcdWI5NzhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWMyZGNcdWJiZmNcdWI0ZTRcdWM3NDAgXHViMjA0XHVhYzAwIFx1YjljOFx1ZDUzY1x1YzU0NFx1Yzc3OFx1YzljMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOWM0XHVkNTg5XHVkNTU4XHViYTc0XHVjMTFjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MThcdWJhNzRcdWMxMWMgXHVkNjA0XHVjN2FjIE5cdWJhODVcdWM3NTggXHVjMGI0XHVjNTQ0XHViMGE4XHVjNzQwIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWIyMDRcdWFjMDAgXHViOWM4XHVkNTNjXHVjNTQ0XHVjNzc4XHVjOWMwIFx1YmMxZFx1ZDYwMFx1YjBiNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzJkY1x1YmJmY1x1YjRlNFx1Yzc0MCBcdWM5ZDBcdWM3OTFcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YjljOFx1ZDUzY1x1YzU0NFx1Yjk3YyBcdWM5YzBcdWJhYTlcdWQ1NThcdWFjZTAgXHViOWM4XHVkNTNjXHVjNTQ0XHViODVjIFx1YzljMFx1YmFhOVx1YjQxYyBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNTQ0XHViYjM0XHVhYzgzXHViM2M0IFx1YmFhOFx1Yjk3NFx1YjI5NCBcdWNjOTksIFx1YjljOFx1ZDUzY1x1YzU0NFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVjYzk5XHVjNzQ0Jm5ic3A7XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyMDRcdWFjMDAgXHViOWM4XHVkNTNjXHVjNTQ0XHVjNzc4XHVjOWMwIFx1YmFhOFx1Yjk3YyBcdWI1NGMsIFx1Yzc3NCBcdWNjMzhcdWFjMDBcdWM3OTBcdWI0ZTQgXHVjOTExXHVjNWQwIFx1YjljOFx1ZDUzY1x1YzU0NFx1YWMwMCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViYTg3IFx1YmE4NVx1Yzc3NFx1YjA5OCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz8mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IE4oMiAmbHQ7IE4gJmx0OyA1MDAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LiZuYnNwO1x1Y2MzOFx1YWMwMFx1Yzc5MFx1YjRlNFx1Yzc0MCAxXHVjNWQwXHVjMTFjIE5cdWFlNGNcdWM5YzBcdWM3NTggXHVjMjE4XHViOTdjIFx1YjRmMVx1YzVkMCBcdWJkOTlcdWM3NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAmbmJzcDtLXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWI0ZjFcdWJjODhcdWQ2MzhcdWFjMDAgS1x1YmM4OFx1Yzc3OCZuYnNwO1x1Y2MzOFx1YWMwMFx1Yzc5MFx1YzVkMCBcdWM3NThcdWQ1NzQgXHVjOWMwXHViYWE5XHViMmY5XHVkNTVjIFx1YjRmMVx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC4gKFx1Yzc5MFx1YWUzMFx1Yzc5MFx1YzJlMFx1Yzc0MCBcdWM5YzBcdWJhYTlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzc0IFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YzExYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViOWM4XHVkNTNjXHVjNTQ0XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWM3NzhcdWM2ZDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExYyBcdWI5YzhcdWQ1M2NcdWM1NDRcdWM3N2MgXHVhYzgzXHVjNzc0XHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1YjQxOFx1YjI5NCBcdWNjMzhcdWFjMDBcdWM3OTBcdWIyOTQmbmJzcDsyXHViYzg4XHVhY2ZjIDNcdWJjODhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YzViNFx1YjI5MCBcdWIyMDRcdWFkNmNcdWIwOTggXHViOWM4XHVkNTNjXHVjNTQ0XHViODVjIFx1YzBkZFx1YWMwMVx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YzhcdWQ1M2NcdWM1NDRcdWIwN2NcdWI5YWNcdWIyOTQgXHVjMTFjXHViODVjIFx1YjIwNFx1YWQ3MFx1YzljMCBcdWM1NDRcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMxMWNcdWI4NWMgXHVjOWMwXHViYWE5XHVjNzQ0IFx1YzU0OCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTYwIFx1YWM4M1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNTQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTUFGSUpBIiwiZGVzY3JpcHRpb24iOiI8cD5NYWZpYSBpcyBhIHNvY2lhbCBnYW1lIHBsYXllZCBmcmVxdWVudGx5IGJ5IGhpZ2ggc2Nob29sIGNvbXBldGl0b3JzIGluIGluZm9ybWF0aWNzIG9uIHN1bW1lciBhbmQgd2ludGVyIGNhbXBzIGFuZCBuYXRpb25hbCBjb21wZXRpdGlvbnMsIHVzdWFsbHkgdmVyeSBsYXRlIGF0IG5pZ2h0LCBkcmlua2luZyB2YXJpb3VzIGZydWl0IHNvZGFzLiBUaGlzIGdhbWUgaXMgbm90IGFib3V0IHdpbm5pbmcsIGl0JiMzOTtzIGFib3V0IGxvcyB0YWtpbmcgcGFydCwgbGlrZSBpbiBjb21wZXRpdGlvbnMuPFwvcD5cclxuXHJcbjxwPlRvIHNvbHZlIHRoaXMgdGFzaywgeW91IGRvbiYjMzk7dCBuZWVkIHRvIGtub3cgdGhlIHJ1bGVzIG9mIG1hZmlhOyBhbGwgeW91IG5lZWQgdG8ga25vdyBpcyB0aGF0IHNvbWUgb2YgdGhlIHBsYXllcnMgYXJlICZxdW90O21vYnN0ZXJzJnF1b3Q7IGFuZCB0aGUgcmVzdCBhcmUgJnF1b3Q7Y2l2aWxpYW5zJnF1b3Q7LiBUaGUgbW9ic3RlcnMga25vdyB3aG8gaXMgd2hvLCBidXQgdGhlIGNpdmlsaWFucyBkb24mIzM5O3QuIFRoZSBjaXZpbGlhbnMgYXJlIHRyeWluZyB0byBmaWd1cmUgb3V0IHdobyB0aGUgbW9ic3RlcnMgYXJlIGR1cmluZyB0aGUgZ2FtZS48XC9wPlxyXG5cclxuPHA+SW4gdGhlIGN1cnJlbnQgcm91bmQgb2YgdGhlIGdhbWUsIG91dCBvZiBOIHN1cnZpdmluZyBwbGF5ZXJzIHNvIGZhciwgZWFjaCBvbmUgaGFzIGFjY3VzZWQgZXhhY3RseSBvbmUgb3RoZXIgcGxheWVyIHNheWluZyB0aGF0IGhlIGlzIHRoZSBtb2JzdGVyLiBUaGUgY2l2aWxpYW5zIHdlcmUgb25seSBndWVzc2luZyBhbmQgdGhlIG1vYnN0ZXJzIGhhdmUgYWNjdXNlZCBjaXZpbGlhbnMsIHByZXRlbmRpbmcgdG8ga25vdyBub3RoaW5nLjxcL3A+XHJcblxyXG48cD5Ob3Qga25vd2luZyB3aG8gdGhlIG1vYnN0ZXJzIGFyZSwgYnV0IGtub3dpbmcgd2hvIGFjY3VzZWQgd2hvbSwgZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIHBvc3NpYmxlIG51bWJlciBvZiBtb2JzdGVycyBhbW9uZyB0aGVzZSBwbGF5ZXJzITxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMiAmbHQ7IE4gJmx0OyA1MDAgMDAwKSwgdGhlIG51bWJlciBvZiBwbGF5ZXJzLiBUaGUgcGxheWVycyBhcmUgbGFiZWxlZCB3aXRoIGludGVnZXJzIGZyb20gMSB0byBOLjxcL3A+XHJcblxyXG48cD5UaGUgSzxzdXA+dGg8XC9zdXA+IGxpbmUgb2YgaW5wdXQsIG91dCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMsIGNvbnRhaW5zIHRoZSBsYWJlbCBvZiB0aGUgcGxheWVyIGFjY3VzZWQgYnkgdGhlIHBsYXllciBLLiAoTm8gcGxheWVyIGNhbiBhY2N1c2UgdGhlbXNlbHZlcy4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbWF4aW11bSBwb3NzaWJsZSBudW1iZXIgb2YgbW9ic3RlcnMuPFwvcD5cclxuIiwiaGludCI6IjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIGZpcnN0IHNhbXBsZSB0ZXN0OiBUaGUgbW9ic3RlciBjYW4gYmUgcGxheWVyIDIgYW5kIDMuPFwvcD5cclxuXHJcbjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIHNlY29uZCBzYW1wbGUgdGVzdDogVGhlIG1vYnN0ZXIgY2FuIGJlIGFueSBwbGF5ZXIsIGJ1dCB0aGVyZSBjYW5ub3QgYmUgbW9yZSBvZiB0aGVtIGJlY2F1c2UgdGhhdCB3b3VsZCBtZWFuIHRoYXQgb25lIG9mIHRoZW0gYWNjdXNlZCB0aGUgb3RoZXIuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=