시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB276971248724.229%

문제

홍준이는 프로그래밍 대회를 개최했다. 이 대회는 사람들이 팀을 이루어서 참가해야 하며, 팀원의 수는 홍준이가 정해준다. 팀원이 홍준이가 정한 값보다 부족하다면, 그 팀은 대회에 참여할 수 없다. 모든 팀은 같은 수의 팀원으로 이루어져 있다.

대회에 참여 의사를 밝힌 학교는 총 N개이다. 각 학교는 모든 학생이 참여할 수 있는 경우에만 대회에 참가한다. 즉, 남는 사람 없이 모든 학생이 팀에 들어갈 수 있어야 한다.

대회는 예선과 본선으로 구성되어 있다. 모든 팀은 같은 학교 소속으로 이루어져 있어야 한다. 예선에서 각 학교 1등팀만 본선에 진출한다. 

홍준이의 대회는 올해가 첫 해이기 때문에, 많은 관심이 필요하다. 따라서, 본선에 참가하는 사람의 수를 최대가 되도록 팀원의 수를 정하려고 한다. 또, 본선이 지루해지는 것을 막기 위해 적어도 두 팀이 본선에 참가할 수 있어야 한다.

홍준이가 팀원을 몇 명으로 정해야 본선에 참가하는 사람의 수가 최대가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 홍준이의 대회에 참여 의사를 밝힌 학교의 수 N (2 ≤ N ≤ 200,000)이 주어진다.

둘째 줄에는 각 학교 학생의 수가 주어진다. 학생의 수는 구간 [1, 2,000,000]에 포함된다.

출력

첫째 줄에 홍준이의 대회 본선에 참가하는 사람의 수의 최댓값을 출력한다.

예제 입력 1

3
1 2 4

예제 출력 1

4

예제 입력 2

2
1 5

예제 출력 2

2

예제 입력 3

5
4 6 3 8 9

예제 출력 3

9

힌트

첫 번째 예제의 경우 홍준이가 한 팀당 두 명으로 결정하면, 2번과 3번 학교가 참가할 수 있다.

W3sicHJvYmxlbV9pZCI6IjEyMjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NGRcdWM5MDAgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1YjMwMFx1ZDY4YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNjRkXHVjOTAwXHVjNzc0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTg4XHViMmU0LiBcdWM3NzQgXHViMzAwXHVkNjhjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWQzMDBcdWM3NDQgXHVjNzc0XHViOGU4XHVjNWI0XHVjMTFjIFx1Y2MzOFx1YWMwMFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1ZDMwMFx1YzZkMFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVkNjRkXHVjOTAwXHVjNzc0XHVhYzAwIFx1YzgxNVx1ZDU3NFx1YzkwMFx1YjJlNC4gXHVkMzAwXHVjNmQwXHVjNzc0IFx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YWMwMCBcdWM4MTVcdWQ1NWMgXHVhYzEyXHViY2Y0XHViMmU0IFx1YmQ4MFx1Yzg3MVx1ZDU1OFx1YjJlNFx1YmE3NCwgXHVhZGY4IFx1ZDMwMFx1Yzc0MCBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjYzM4XHVjNWVjXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWQzMDBcdWM3NDAgXHVhYzE5XHVjNzQwIFx1YzIxOFx1Yzc1OCBcdWQzMDBcdWM2ZDBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMzAwXHVkNjhjXHVjNWQwIFx1Y2MzOFx1YzVlYyBcdWM3NThcdWMwYWNcdWI5N2MgXHViYzFkXHVkNzhjIFx1ZDU1OVx1YWQ1MFx1YjI5NCBcdWNkMWQgTlx1YWMxY1x1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1ZDU1OVx1YWQ1MFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHVjNzc0IFx1Y2MzOFx1YzVlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjljYyBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YjBhOFx1YjI5NCBcdWMwYWNcdWI3OGMgXHVjNWM2XHVjNzc0IFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NzQmbmJzcDtcdWQzMDBcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzMDBcdWQ2OGNcdWIyOTQgXHVjNjA4XHVjMTIwXHVhY2ZjIFx1YmNmOFx1YzEyMFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVkMzAwXHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWQ1NTlcdWFkNTAgXHVjMThjXHVjMThkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWMxMjBcdWM1ZDBcdWMxMWMgXHVhYzAxIFx1ZDU1OVx1YWQ1MCAxXHViNGYxXHVkMzAwXHViOWNjIFx1YmNmOFx1YzEyMFx1YzVkMCBcdWM5YzRcdWNkOWNcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1ZDY0ZFx1YzkwMFx1Yzc3NFx1Yzc1OCBcdWIzMDBcdWQ2OGNcdWIyOTQgXHVjNjJjXHVkNTc0XHVhYzAwIFx1Y2NhYiBcdWQ1NzRcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWI5Y2VcdWM3NDAgXHVhZDAwXHVjMmVjXHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWJjZjhcdWMxMjBcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWQzMDBcdWM2ZDBcdWM3NTggXHVjMjE4XHViOTdjIFx1YzgxNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHViY2Y4XHVjMTIwXHVjNzc0IFx1YzljMFx1YjhlOFx1ZDU3NFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NDQgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHViNDUwIFx1ZDMwMFx1Yzc3NCBcdWJjZjhcdWMxMjBcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2NGRcdWM5MDBcdWM3NzRcdWFjMDAgXHVkMzAwXHVjNmQwXHVjNzQ0IFx1YmE4NyBcdWJhODVcdWM3M2NcdWI4NWMgXHVjODE1XHVkNTc0XHVjNTdjIFx1YmNmOFx1YzEyMFx1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ2NGRcdWM5MDBcdWM3NzRcdWM3NTggXHViMzAwXHVkNjhjXHVjNWQwIFx1Y2MzOFx1YzVlYyBcdWM3NThcdWMwYWNcdWI5N2MgXHViYzFkXHVkNzhjIFx1ZDU1OVx1YWQ1MFx1Yzc1OCBcdWMyMTggTiAoMiAmbGU7IE4gJmxlOyAyMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1ZDU1OVx1YWQ1MCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWFkNmNcdWFjMDQgWzEsIDIsMDAwLDAwMF1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNjRkXHVjOTAwXHVjNzc0XHVjNzU4IFx1YjMwMFx1ZDY4YyBcdWJjZjhcdWMxMjBcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwIFx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YWMwMCBcdWQ1NWMgXHVkMzAwXHViMmY5IFx1YjQ1MCBcdWJhODVcdWM3M2NcdWI4NWMgXHVhY2IwXHVjODE1XHVkNTU4XHViYTc0LCAyXHViYzg4XHVhY2ZjIDNcdWJjODggXHVkNTU5XHVhZDUwXHVhYzAwIFx1Y2MzOFx1YWMwMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTIyMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9SR0FOSVpBVE9SIiwiZGVzY3JpcHRpb24iOiI8cD5VbmV4cGVjdGVkIHByb2JsZW1zIHdpdGggbGF3IGVuZm9yY2VtZW50IGhhdmUgY29udmluY2VkIE1pcmtvIHRvIHRha2UgdXAgYSBsZXNzIGx1Y3JhdGl2ZSBidXQgbGVzcyBtb3JhbGx5IGFtYmlndW91cyBjYXJlZXI6IGhlIGhhcyBiZWNvbWUgdGhlIGNoaWVmIG9yZ2FuaXplciBvZiBhIHRlYW0gY29tcHV0ZXIgc2NpZW5jZSBjb250ZXN0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgTiBDUyBjbHVicyB0aGF0IHdpc2ggdG8gcGFydGljaXBhdGUgaW4gdGhlIGNvbnRlc3QuIFRoZSBwcmVzaWRlbnRzIG9mIHRoZSBjbHVicyBhcmUgcXVpdGUgc3R1YmJvcm4gYW5kIHdpbGwgcGFydGljaXBhdGUgaW4gdGhlIGNvbnRlc3Qgb25seSBpZiB0aGUgY29udGVzdCB0ZWFtIHNpemUgbWFrZXMgaXQgcG9zc2libGUgZm9yIGFsbCBjbHViIG1lbWJlcnMgdG8gcGFydGljaXBhdGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjb250ZXN0IGNvbnNpc3RzIG9mIHR3byByb3VuZHM6IHF1YWxpZmljYXRpb25zIGFuZCBmaW5hbHMuIEFsbCB0ZWFtcyB0aGF0IGFyZSBjb21wZXRpbmcgbXVzdCBoYXZlIGFuIGVxdWFsIG51bWJlciBvZiBtZW1iZXJzIGFuZCBhbGwgbWVtYmVycyBvZiBvbmUgdGVhbSBtdXN0IGJlbG9uZyB0byB0aGUgc2FtZSBjbHViLiBBbnkgbnVtYmVyIG9mIHRlYW1zIGZyb20gZWFjaCBjbHViIGNhbiBwYXJ0aWNpcGF0ZSBpbiB0aGUgcXVhbGlmaWNhdGlvbiByb3VuZCwgYW5kIHRoZSBiZXN0IHRlYW0gZnJvbSBlYWNoIGNsdWIgZWFybnMgYSBzcG90IGluIHRoZSBmaW5hbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIGlzIGF3YXJlIHRoYXQsIHdpdGggYSBuZXcgYW5kIHVucHJvdmVuIGNvbnRlc3QsIGhlIG5lZWRzIHB1YmxpY2l0eS4gRm9yIHRoYXQgcmVhc29uLCBoZSB3YW50cyB0byBzZXQgdGhlIHRlYW0gc2l6ZSBzdWNoIHRoYXQgdGhlIG51bWJlciBvZiBpbmRpdmlkdWFsIHBhcnRpY2lwYW50cyBpbiB0aGUgZmluYWxzIGlzIGFzIGxhcmdlIGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5SZW1lbWJlciwgZWFjaCBjbHViIHRoYXQgcGFydGljaXBhdGVzIGhhcyBhIHJpZ2h0IHRvIG9uZSB0ZWFtIGluIHRoZSBmaW5hbHMuIEZ1cnRoZXJtb3JlLCBhdCBsZWFzdCB0d28gY2x1YnMgbXVzdCBwYXJ0aWNpcGF0ZSBpbiB0aGUgY29udGVzdCwgb3RoZXJ3aXNlIHRoZSBjb250ZXN0IHdvdWxkIGJlIHRvbyBib3JpbmcgdG8gYXR0cmFjdCBzcG9uc29ycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBtYXhpbXVtIHBvc3NpYmxlIG51bWJlciBvZiBwYXJ0aWNpcGFudHMgaW4gdGhlIGZpbmFscyBzbyB0aGF0IE1pcmtvIGNhbiBkb3VibGUgY2hlY2sgaGlzIHRlYW0gc2l6ZSBjaG9pY2UuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDIwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGNsdWJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgZnJvbSB0aGUgaW50ZXJ2YWwgWzEsIDIgMDAwIDAwMF0sIHRoZSBudW1iZXIgb2YgbWVtYmVycyBvZiBlYWNoIGNsdWIuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbWF4aW11bSBwb3NzaWJsZSBudW1iZXIgb2YgZmluYWxpc3RzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgZmlyc3QgZXhhbXBsZTogTWlya28gZGVjaWRlcyBvbiAyIG1lbWJlcnMgcGVyIHRlYW0sIHNvIGNsdWJzIDIgYW5kIDMgcGFydGljaXBhdGUuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #1 5번