시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1348 439 353 37.633%

문제

ICPC 대학의 모든 박사과정 학생은 자신이 발표한 논문과 그 논문들의 인용횟수를 고려한 학위 취득 조건을 만족해야 한다. 이를 위해, ICPC 대학은 q-인덱스라는 값을 정의했다. 이 인덱스는 논문들의 중요도를 측정하기 위해, 가장 많이 인용된 논문들의 개수와 그 논문들의 인용횟수를 이용하여 다음과 같이 정의된다. 한 학생이 발표한 총 n ≥ 1 편의 논문 중에서, k번 이상 인용된 논문이 k편이고 나머지 n − k 편의 논문들 인용회수가 각각 k 번 이하라면, 해당 학생의 q-인덱스는 k이다.

예를 들어, 한 학생이 발표한 논문이 총 5 편이고, 각 논문의 인용횟수가 8, 4, 5, 3, 10 이라 하자. 한 번 이상 인용된 논문이 1 편 이상이지만 나머지 4 편의 논문 중에는 한 번 보다 더 많이 인용된 논문이 존재하기 때문에 q-인덱스는 1 이 아니다. 그리고 모든 논문이 5 번 이상 인용되지 않았기 때문에, 인덱스 값이 5 가 될 수도 없다. 이 학생의 q-인덱스는 결국 4 가 되는 데, 그 이유는 4 번 이상 인용된 논문 4 편이 있고, 나머지 1 편은 4 번 이하의 인용횟수를 갖기 때문이다.

한 학생의 논문들의 인용횟수가 주어지면, 이 학생의 q-인덱스를 계산하는 프로그램을 작성하시오.

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 학생이 발표한 논문의 수 n (1 ≤ n ≤ 1,000)이 주어진다. 다음 줄에는 n 개의 논문들에 대한 인용횟수가 빈 칸을 사이에 두고 차례로 주어진다. 각 인용횟수는 0 이상 10,000 이하의 정수 값이다.

출력

표준 출력으로 답을 출력한다. 주어진 입력에 대한 q-인덱스 (음이 아닌 정수) 값 하나를 출력한다.

예제 입력 1

5
8 4 5 3 10

예제 출력 1

4

예제 입력 2

4
0 0 0 0

예제 출력 2

0

예제 입력 3

6
12 7 6 8 9 10

예제 출력 3

6
W3sicHJvYmxlbV9pZCI6IjEzMzMzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiUS1cdWM3NzhcdWIzNzFcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPklDUEMgXHViMzAwXHVkNTU5XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJjMTVcdWMwYWNcdWFjZmNcdWM4MTUgXHVkNTU5XHVjMGRkXHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWJjMWNcdWQ0NWNcdWQ1NWMgXHViMTdjXHViYjM4XHVhY2ZjIFx1YWRmOCBcdWIxN2NcdWJiMzhcdWI0ZTRcdWM3NTggXHVjNzc4XHVjNmE5XHVkNjlmXHVjMjE4XHViOTdjIFx1YWNlMFx1YjgyNFx1ZDU1YyBcdWQ1NTlcdWM3MDQgXHVjZGU4XHViNGRkIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0LCBJQ1BDIFx1YjMwMFx1ZDU1OVx1Yzc0MCBxLVx1Yzc3OFx1YjM3MVx1YzJhNFx1Yjc3Y1x1YjI5NCBcdWFjMTJcdWM3NDQgXHVjODE1XHVjNzU4XHVkNTg4XHViMmU0LiBcdWM3NzQgXHVjNzc4XHViMzcxXHVjMmE0XHViMjk0IFx1YjE3Y1x1YmIzOFx1YjRlNFx1Yzc1OCBcdWM5MTFcdWM2OTRcdWIzYzRcdWI5N2MgXHVjZTIxXHVjODE1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc3NCBcdWM3NzhcdWM2YTlcdWI0MWMgXHViMTdjXHViYjM4XHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MCBcdWFkZjggXHViMTdjXHViYjM4XHViNGU0XHVjNzU4IFx1Yzc3OFx1YzZhOVx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuIFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViYzFjXHVkNDVjXHVkNTVjIFx1Y2QxZCBuICZnZTsgMSBcdWQzYjhcdWM3NTggXHViMTdjXHViYjM4IFx1YzkxMVx1YzVkMFx1YzExYywga1x1YmM4OCBcdWM3NzRcdWMwYzEgXHVjNzc4XHVjNmE5XHViNDFjIFx1YjE3Y1x1YmIzOFx1Yzc3NCBrXHVkM2I4XHVjNzc0XHVhY2UwIFx1YjA5OFx1YmEzOFx1YzljMCBuICZtaW51czsgayBcdWQzYjhcdWM3NTggXHViMTdjXHViYjM4XHViNGU0IFx1Yzc3OFx1YzZhOVx1ZDY4Y1x1YzIxOFx1YWMwMCBcdWFjMDFcdWFjMDEgayBcdWJjODggXHVjNzc0XHVkNTU4XHViNzdjXHViYTc0LCBcdWQ1NzRcdWIyZjkgXHVkNTU5XHVjMGRkXHVjNzU4IHEtXHVjNzc4XHViMzcxXHVjMmE0XHViMjk0IGtcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViYzFjXHVkNDVjXHVkNTVjIFx1YjE3Y1x1YmIzOFx1Yzc3NCBcdWNkMWQgNSBcdWQzYjhcdWM3NzRcdWFjZTAsIFx1YWMwMSBcdWIxN2NcdWJiMzhcdWM3NTggXHVjNzc4XHVjNmE5XHVkNjlmXHVjMjE4XHVhYzAwIDgsIDQsIDUsIDMsIDEwIFx1Yzc3NFx1Yjc3YyBcdWQ1NThcdWM3OTAuIFx1ZDU1YyBcdWJjODggXHVjNzc0XHVjMGMxIFx1Yzc3OFx1YzZhOVx1YjQxYyBcdWIxN2NcdWJiMzhcdWM3NzQgMSBcdWQzYjggXHVjNzc0XHVjMGMxXHVjNzc0XHVjOWMwXHViOWNjIFx1YjA5OFx1YmEzOFx1YzljMCA0IFx1ZDNiOFx1Yzc1OCBcdWIxN2NcdWJiMzggXHVjOTExXHVjNWQwXHViMjk0IFx1ZDU1YyBcdWJjODggXHViY2Y0XHViMmU0IFx1YjM1NCBcdWI5Y2VcdWM3NzQgXHVjNzc4XHVjNmE5XHViNDFjIFx1YjE3Y1x1YmIzOFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIHEtXHVjNzc4XHViMzcxXHVjMmE0XHViMjk0IDEgXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YmFhOFx1YjRlMCBcdWIxN2NcdWJiMzhcdWM3NzQgNSBcdWJjODggXHVjNzc0XHVjMGMxIFx1Yzc3OFx1YzZhOVx1YjQxOFx1YzljMCBcdWM1NGFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3NzhcdWIzNzFcdWMyYTQgXHVhYzEyXHVjNzc0IDUgXHVhYzAwIFx1YjQyMCBcdWMyMThcdWIzYzQgXHVjNWM2XHViMmU0LiBcdWM3NzQgXHVkNTU5XHVjMGRkXHVjNzU4IHEtXHVjNzc4XHViMzcxXHVjMmE0XHViMjk0IFx1YWNiMFx1YWQ2ZCA0IFx1YWMwMCBcdWI0MThcdWIyOTQgXHViMzcwLCBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IDQgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM3NzhcdWM2YTlcdWI0MWMgXHViMTdjXHViYjM4IDQgXHVkM2I4XHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIDEgXHVkM2I4XHVjNzQwIDQgXHViYzg4IFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM3NzhcdWM2YTlcdWQ2OWZcdWMyMThcdWI5N2MgXHVhYzE2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTVjIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWIxN2NcdWJiMzhcdWI0ZTRcdWM3NTggXHVjNzc4XHVjNmE5XHVkNjlmXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVjNzc0IFx1ZDU1OVx1YzBkZFx1Yzc1OCBxLVx1Yzc3OFx1YjM3MVx1YzJhNFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWJjMWJcdWIyOTRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWJjMWNcdWQ0NWNcdWQ1NWMgXHViMTdjXHViYjM4XHVjNzU4IFx1YzIxOCBuICgxICZsZTsgbiAmbGU7IDEsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgbiBcdWFjMWNcdWM3NTggXHViMTdjXHViYjM4XHViNGU0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM3NzhcdWM2YTlcdWQ2OWZcdWMyMThcdWFjMDAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM3NzhcdWM2YTlcdWQ2OWZcdWMyMThcdWIyOTQgMCBcdWM3NzRcdWMwYzEgMTAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMTggXHVhYzEyXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDQ1Y1x1YzkwMCBcdWNkOWNcdWI4MjVcdWM3M2NcdWI4NWMgXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWIzMDBcdWQ1NWMgcS1cdWM3NzhcdWIzNzFcdWMyYTQgKFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4KSBcdWFjMTIgXHVkNTU4XHViMDk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMzMzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlEtSW5kZXgiLCJkZXNjcmlwdGlvbiI6IjxwPkFueSBQaC5ELiBjYW5kaWRhdGUgaW4gSUNQQyBVbml2ZXJzaXR5IHNob3VsZCBxdWFsaWZ5IGZvciBoaXNcL2hlciBQaC5ELiBkZWdyZWUgaW4gdGVybXMgb2YgdGhlIG51bWJlciBvZiBoaXNcL2hlciBwYXBlcnMgYW5kIHRoZWlyIGNpdGF0aW9ucy4gRm9yIHRoaXMsIHRoZSB1bml2ZXJzaXR5IGhhcyBkZWZpbmVkIGEgcXVhbnRpdHksIGNhbGxlZCBxLWluZGV4LiBUbyBtZWFzdXJlIHRoZSBpbXBvcnRhbmNlIG9mIHRoZSBwYXBlcnMsIHRoaXMgaW5kZXggaXMgYmFzZWQgb24gdGhlIHNldCBvZiB0aGUgbW9zdCBjaXRlZCBwYXBlcnMgYW5kIHRoZSBudW1iZXIgb2YgY2l0YXRpb25zIHRoYXQgdGhleSBoYXZlIHJlY2VpdmVkIGluIG90aGVyIHBhcGVycy4gQSBjYW5kaWRhdGUgd2hvIGhhcyBwdWJsaXNoZWQgdG90YWwgbiAmZ2U7IDEgcGFwZXJzIGhhcyBxaW5kZXggayBpZiBrIG9mIG4gcGFwZXJzIGhhdmUgYXQgbGVhc3QgayBjaXRhdGlvbnMgZWFjaCwgYW5kIHRoZSBvdGhlciBuICZtaW51czsgayBwYXBlcnMgaGF2ZSBhdCBtb3N0IGsgY2l0YXRpb25zIGVhY2guPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB3ZSBzdXBwb3NlIHRoYXQgYSBjYW5kaWRhdGUgaGFzIHB1Ymxpc2hlZCBmaXZlIHBhcGVycywgZWFjaCBjaXRlZCA4LCA0LCA1LCAzLCAxMCB0aW1lcyBieSBvdGhlciBwYXBlcnMuIFRoZSBjYW5kaWRhdGUgaGFzIGEgcGFwZXIgd2hvc2UgY2l0YXRpb24gaXMgYXQgbGVhc3Qgb25lLCBidXQgdGhlIG90aGVyIGZvdXIgcGFwZXJzIGFyZSBjaXRlZCBtb3JlIHRoYW4gb25jZSwgc28gdGhlIHEtaW5kZXggaXMgbm90IDEuIEZvciBhbGwgZml2ZSBwYXBlcnMsIHRoZXJlIGFyZSB0d28gcGFwZXJzIHdob3NlIGNpdGF0aW9ucyBhcmUgbGVzcyB0aGFuIDUsIHNvIHRoZSBxLWluZGV4IGlzIG5vdCA1LiBXZSBmaW5hbGx5IGtub3cgdGhhdCB0aGUgcS1pbmRleCBiZWNvbWVzIDQgYmVjYXVzZSB0aGVyZSBhcmUgZm91ciBwYXBlcnMgY2l0ZWQgYXQgbGVhc3QgZm91ciB0aW1lcyBhbmQgdGhlIG90aGVyIG9uZSBwYXBlciBjaXRlZCBhdCBtb3N0IGZvdXIgdGltZXMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGNpdGF0aW9uIG51bWJlcnMgb2YgdGhlIHBhcGVycyBwdWJsaXNoZWQgYnkgYSBjYW5kaWRhdGUsIHlvdSB3cml0ZSBhIHByb2dyYW0gdG8gY2FsY3VsYXRlIHRoZSBxLWluZGV4LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIsIG4gKDEgJmxlOyBuICZsZTsgMSwwMDApLCB3aGVyZSBuIGlzIHRoZSBudW1iZXIgb2YgcGFwZXJzIHB1Ymxpc2hlZCBieSBhIFBoLkQuIGNhbmRpZGF0ZS4gVGhlIG5leHQgbGluZSBjb250YWlucyB0aGUgY2l0YXRpb24gbnVtYmVycyBvZiB0aGUgbiBwYXBlcnMsIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBFYWNoIGNpdGF0aW9uIG51bWJlciBpcyBhbiBpbnRlZ2VyIGJldHdlZW4gMCBhbmQgMTAsMDAwLCBpbmNsdXNpdmVseS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciB0aGUgaW5wdXQuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBxLWluZGV4LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==