시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 230 55 43 25.146%

문제

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

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

게임이 진행되면서 현재 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+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIFx1YjljOFx1ZDUzY1x1YzU0NFx1Yzc3YyBcdWFjODNcdWM3NzRcdWI3N2NcdWFjZTAgXHVjMGRkXHVhYzAxXHViNDE4XHViMjk0IFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjI5NCZuYnNwOzJcdWJjODhcdWFjZmMgM1x1YmM4OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWM1YjRcdWIyOTAgXHViMjA0XHVhZDZjXHViMDk4IFx1YjljOFx1ZDUzY1x1YzU0NFx1Yjg1YyBcdWMwZGRcdWFjMDFcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVkNTNjXHVjNTQ0XHViMDdjXHViOWFjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyMDRcdWFkNzBcdWM5YzAgXHVjNTQ0XHViMjk0IFx1YzBjMVx1ZDY2OVx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMTFjXHViODVjIFx1YzljMFx1YmFhOVx1Yzc0NCBcdWM1NDggXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDU0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1BRklKQSIsImRlc2NyaXB0aW9uIjoiPHA+TWFmaWEgaXMgYSBzb2NpYWwgZ2FtZSBwbGF5ZWQgZnJlcXVlbnRseSBieSBoaWdoIHNjaG9vbCBjb21wZXRpdG9ycyBpbiBpbmZvcm1hdGljcyBvbiBzdW1tZXIgYW5kIHdpbnRlciBjYW1wcyBhbmQgbmF0aW9uYWwgY29tcGV0aXRpb25zLCB1c3VhbGx5IHZlcnkgbGF0ZSBhdCBuaWdodCwgZHJpbmtpbmcgdmFyaW91cyBmcnVpdCBzb2Rhcy4gVGhpcyBnYW1lIGlzIG5vdCBhYm91dCB3aW5uaW5nLCBpdCYjMzk7cyBhYm91dCBsb3MgdGFraW5nIHBhcnQsIGxpa2UgaW4gY29tcGV0aXRpb25zLjxcL3A+XHJcblxyXG48cD5UbyBzb2x2ZSB0aGlzIHRhc2ssIHlvdSBkb24mIzM5O3QgbmVlZCB0byBrbm93IHRoZSBydWxlcyBvZiBtYWZpYTsgYWxsIHlvdSBuZWVkIHRvIGtub3cgaXMgdGhhdCBzb21lIG9mIHRoZSBwbGF5ZXJzIGFyZSAmcXVvdDttb2JzdGVycyZxdW90OyBhbmQgdGhlIHJlc3QgYXJlICZxdW90O2NpdmlsaWFucyZxdW90Oy4gVGhlIG1vYnN0ZXJzIGtub3cgd2hvIGlzIHdobywgYnV0IHRoZSBjaXZpbGlhbnMgZG9uJiMzOTt0LiBUaGUgY2l2aWxpYW5zIGFyZSB0cnlpbmcgdG8gZmlndXJlIG91dCB3aG8gdGhlIG1vYnN0ZXJzIGFyZSBkdXJpbmcgdGhlIGdhbWUuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBjdXJyZW50IHJvdW5kIG9mIHRoZSBnYW1lLCBvdXQgb2YgTiBzdXJ2aXZpbmcgcGxheWVycyBzbyBmYXIsIGVhY2ggb25lIGhhcyBhY2N1c2VkIGV4YWN0bHkgb25lIG90aGVyIHBsYXllciBzYXlpbmcgdGhhdCBoZSBpcyB0aGUgbW9ic3Rlci4gVGhlIGNpdmlsaWFucyB3ZXJlIG9ubHkgZ3Vlc3NpbmcgYW5kIHRoZSBtb2JzdGVycyBoYXZlIGFjY3VzZWQgY2l2aWxpYW5zLCBwcmV0ZW5kaW5nIHRvIGtub3cgbm90aGluZy48XC9wPlxyXG5cclxuPHA+Tm90IGtub3dpbmcgd2hvIHRoZSBtb2JzdGVycyBhcmUsIGJ1dCBrbm93aW5nIHdobyBhY2N1c2VkIHdob20sIGRldGVybWluZSB0aGUgbWF4aW11bSBwb3NzaWJsZSBudW1iZXIgb2YgbW9ic3RlcnMgYW1vbmcgdGhlc2UgcGxheWVycyE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDIgJmx0OyBOICZsdDsgNTAwIDAwMCksIHRoZSBudW1iZXIgb2YgcGxheWVycy4gVGhlIHBsYXllcnMgYXJlIGxhYmVsZWQgd2l0aCBpbnRlZ2VycyBmcm9tIDEgdG8gTi48XC9wPlxyXG5cclxuPHA+VGhlIEs8c3VwPnRoPFwvc3VwPiBsaW5lIG9mIGlucHV0LCBvdXQgb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzLCBjb250YWlucyB0aGUgbGFiZWwgb2YgdGhlIHBsYXllciBhY2N1c2VkIGJ5IHRoZSBwbGF5ZXIgSy4gKE5vIHBsYXllciBjYW4gYWNjdXNlIHRoZW1zZWx2ZXMuKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1heGltdW0gcG9zc2libGUgbnVtYmVyIG9mIG1vYnN0ZXJzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBmaXJzdCBzYW1wbGUgdGVzdDogVGhlIG1vYnN0ZXIgY2FuIGJlIHBsYXllciAyIGFuZCAzLjxcL3A+XHJcblxyXG48cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBzZWNvbmQgc2FtcGxlIHRlc3Q6IFRoZSBtb2JzdGVyIGNhbiBiZSBhbnkgcGxheWVyLCBidXQgdGhlcmUgY2Fubm90IGJlIG1vcmUgb2YgdGhlbSBiZWNhdXNlIHRoYXQgd291bGQgbWVhbiB0aGF0IG9uZSBvZiB0aGVtIGFjY3VzZWQgdGhlIG90aGVyLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d