시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1844 596 476 35.952%

문제

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
W3sicHJvYmxlbV9pZCI6IjEzMzMzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiUS1cdWM3NzhcdWIzNzFcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPklDUEMgXHViMzAwXHVkNTU5XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJjMTVcdWMwYWNcdWFjZmNcdWM4MTUgXHVkNTU5XHVjMGRkXHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWJjMWNcdWQ0NWNcdWQ1NWMgXHViMTdjXHViYjM4XHVhY2ZjIFx1YWRmOCBcdWIxN2NcdWJiMzhcdWI0ZTRcdWM3NTggXHVjNzc4XHVjNmE5XHVkNjlmXHVjMjE4XHViOTdjIFx1YWNlMFx1YjgyNFx1ZDU1YyBcdWQ1NTlcdWM3MDQgXHVjZGU4XHViNGRkIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0LCBJQ1BDIFx1YjMwMFx1ZDU1OVx1Yzc0MCBxLVx1Yzc3OFx1YjM3MVx1YzJhNFx1Yjc3Y1x1YjI5NCBcdWFjMTJcdWM3NDQgXHVjODE1XHVjNzU4XHVkNTg4XHViMmU0LiBcdWM3NzQgXHVjNzc4XHViMzcxXHVjMmE0XHViMjk0IFx1YjE3Y1x1YmIzOFx1YjRlNFx1Yzc1OCBcdWM5MTFcdWM2OTRcdWIzYzRcdWI5N2MgXHVjZTIxXHVjODE1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc3NCBcdWM3NzhcdWM2YTlcdWI0MWMgXHViMTdjXHViYjM4XHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MCBcdWFkZjggXHViMTdjXHViYjM4XHViNGU0XHVjNzU4IFx1Yzc3OFx1YzZhOVx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuIFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViYzFjXHVkNDVjXHVkNTVjIFx1Y2QxZCBuICZnZTsgMSBcdWQzYjhcdWM3NTggXHViMTdjXHViYjM4IFx1YzkxMVx1YzVkMFx1YzExYywga1x1YmM4OCBcdWM3NzRcdWMwYzEgXHVjNzc4XHVjNmE5XHViNDFjIFx1YjE3Y1x1YmIzOFx1Yzc3NCBrXHVkM2I4IFx1Yzc3NFx1YzBjMVx1Yzc3NFx1YWNlMCBcdWIwOThcdWJhMzhcdWM5YzAgbiAmbWludXM7IGsgXHVkM2I4XHVjNzU4IFx1YjE3Y1x1YmIzOFx1YjRlNCBcdWM3NzhcdWM2YTlcdWQ2OGNcdWMyMThcdWFjMDAgXHVhYzAxXHVhYzAxIGsgXHViYzg4IFx1Yzc3NFx1ZDU1OFx1Yjc3Y1x1YmE3NCwgXHVkNTc0XHViMmY5IFx1ZDU1OVx1YzBkZFx1Yzc1OCBxLVx1Yzc3OFx1YjM3MVx1YzJhNFx1YjI5NCBrXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQ1NWMgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YmMxY1x1ZDQ1Y1x1ZDU1YyBcdWIxN2NcdWJiMzhcdWM3NzQgXHVjZDFkIDUgXHVkM2I4XHVjNzc0XHVhY2UwLCBcdWFjMDEgXHViMTdjXHViYjM4XHVjNzU4IFx1Yzc3OFx1YzZhOVx1ZDY5Zlx1YzIxOFx1YWMwMCA4LCA0LCA1LCAzLCAxMCBcdWM3NzRcdWI3N2MgXHVkNTU4XHVjNzkwLiBcdWQ1NWMgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM3NzhcdWM2YTlcdWI0MWMgXHViMTdjXHViYjM4XHVjNzc0IDEgXHVkM2I4IFx1Yzc3NFx1YzBjMVx1Yzc3NFx1YzljMFx1YjljYyBcdWIwOThcdWJhMzhcdWM5YzAgNCBcdWQzYjhcdWM3NTggXHViMTdjXHViYjM4IFx1YzkxMVx1YzVkMFx1YjI5NCBcdWQ1NWMgXHViYzg4IFx1YmNmNFx1YjJlNCBcdWIzNTQgXHViOWNlXHVjNzc0IFx1Yzc3OFx1YzZhOVx1YjQxYyBcdWIxN2NcdWJiMzhcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBxLVx1Yzc3OFx1YjM3MVx1YzJhNFx1YjI5NCAxIFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWJhYThcdWI0ZTAgXHViMTdjXHViYjM4XHVjNzc0IDUgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM3NzhcdWM2YTlcdWI0MThcdWM5YzAgXHVjNTRhXHVjNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzc4XHViMzcxXHVjMmE0IFx1YWMxMlx1Yzc3NCA1IFx1YWMwMCBcdWI0MjAgXHVjMjE4XHViM2M0IFx1YzVjNlx1YjJlNC4gXHVjNzc0IFx1ZDU1OVx1YzBkZFx1Yzc1OCBxLVx1Yzc3OFx1YjM3MVx1YzJhNFx1YjI5NCBcdWFjYjBcdWFkNmQgNCBcdWFjMDAgXHViNDE4XHViMjk0IFx1YjM3MCwgXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCA0IFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVjNzc4XHVjNmE5XHViNDFjIFx1YjE3Y1x1YmIzOCA0IFx1ZDNiOFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCAxIFx1ZDNiOFx1Yzc0MCA0IFx1YmM4OCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzc4XHVjNmE5XHVkNjlmXHVjMjE4XHViOTdjIFx1YWMxNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NTggXHViMTdjXHViYjM4XHViNGU0XHVjNzU4IFx1Yzc3OFx1YzZhOVx1ZDY5Zlx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsIFx1Yzc3NCBcdWQ1NTlcdWMwZGRcdWM3NTggcS1cdWM3NzhcdWIzNzFcdWMyYTRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVjNzg1XHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViYzFiXHViMjk0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViYzFjXHVkNDVjXHVkNTVjIFx1YjE3Y1x1YmIzOFx1Yzc1OCBcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyAxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IG4gXHVhYzFjXHVjNzU4IFx1YjE3Y1x1YmIzOFx1YjRlNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNzc4XHVjNmE5XHVkNjlmXHVjMjE4XHVhYzAwIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWNjMjhcdWI4NDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjNzc4XHVjNmE5XHVkNjlmXHVjMjE4XHViMjk0IDAgXHVjNzc0XHVjMGMxIDEwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4IFx1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ0NWNcdWM5MDAgXHVjZDljXHViODI1XHVjNzNjXHViODVjIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzhmY1x1YzViNFx1YzljNCBcdWM3ODVcdWI4MjVcdWM1ZDAgXHViMzAwXHVkNTVjIHEtXHVjNzc4XHViMzcxXHVjMmE0IChcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOCkgXHVhYzEyIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTMzMzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJRLUluZGV4IiwiZGVzY3JpcHRpb24iOiI8cD5BbnkgUGguRC4gY2FuZGlkYXRlIGluIElDUEMgVW5pdmVyc2l0eSBzaG91bGQgcXVhbGlmeSBmb3IgaGlzXC9oZXIgUGguRC4gZGVncmVlIGluIHRlcm1zIG9mIHRoZSBudW1iZXIgb2YgaGlzXC9oZXIgcGFwZXJzIGFuZCB0aGVpciBjaXRhdGlvbnMuIEZvciB0aGlzLCB0aGUgdW5pdmVyc2l0eSBoYXMgZGVmaW5lZCBhIHF1YW50aXR5LCBjYWxsZWQgcS1pbmRleC4gVG8gbWVhc3VyZSB0aGUgaW1wb3J0YW5jZSBvZiB0aGUgcGFwZXJzLCB0aGlzIGluZGV4IGlzIGJhc2VkIG9uIHRoZSBzZXQgb2YgdGhlIG1vc3QgY2l0ZWQgcGFwZXJzIGFuZCB0aGUgbnVtYmVyIG9mIGNpdGF0aW9ucyB0aGF0IHRoZXkgaGF2ZSByZWNlaXZlZCBpbiBvdGhlciBwYXBlcnMuIEEgY2FuZGlkYXRlIHdobyBoYXMgcHVibGlzaGVkIHRvdGFsIG4gJmdlOyAxIHBhcGVycyBoYXMgcS1pbmRleCBrIGlmIGsgb2YgbiBwYXBlcnMgaGF2ZSBhdCBsZWFzdCBrIGNpdGF0aW9ucyBlYWNoLCBhbmQgdGhlIG90aGVyIG4gJm1pbnVzOyBrIHBhcGVycyBoYXZlIGF0IG1vc3QgayBjaXRhdGlvbnMgZWFjaC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHdlIHN1cHBvc2UgdGhhdCBhIGNhbmRpZGF0ZSBoYXMgcHVibGlzaGVkIGZpdmUgcGFwZXJzLCBlYWNoIGNpdGVkIDgsIDQsIDUsIDMsIDEwIHRpbWVzIGJ5IG90aGVyIHBhcGVycy4gVGhlIGNhbmRpZGF0ZSBoYXMgYSBwYXBlciB3aG9zZSBjaXRhdGlvbiBpcyBhdCBsZWFzdCBvbmUsIGJ1dCB0aGUgb3RoZXIgZm91ciBwYXBlcnMgYXJlIGNpdGVkIG1vcmUgdGhhbiBvbmNlLCBzbyB0aGUgcS1pbmRleCBpcyBub3QgMS4gRm9yIGFsbCBmaXZlIHBhcGVycywgdGhlcmUgYXJlIHR3byBwYXBlcnMgd2hvc2UgY2l0YXRpb25zIGFyZSBsZXNzIHRoYW4gNSwgc28gdGhlIHEtaW5kZXggaXMgbm90IDUuIFdlIGZpbmFsbHkga25vdyB0aGF0IHRoZSBxLWluZGV4IGJlY29tZXMgNCBiZWNhdXNlIHRoZXJlIGFyZSBmb3VyIHBhcGVycyBjaXRlZCBhdCBsZWFzdCBmb3VyIHRpbWVzIGFuZCB0aGUgb3RoZXIgb25lIHBhcGVyIGNpdGVkIGF0IG1vc3QgZm91ciB0aW1lcy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gY2l0YXRpb24gbnVtYmVycyBvZiB0aGUgcGFwZXJzIHB1Ymxpc2hlZCBieSBhIGNhbmRpZGF0ZSwgeW91IHdyaXRlIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUgdGhlIHEtaW5kZXguPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciwgbiAoMSAmbGU7IG4gJmxlOyAxLDAwMCksIHdoZXJlIG4gaXMgdGhlIG51bWJlciBvZiBwYXBlcnMgcHVibGlzaGVkIGJ5IGEgUGguRC4gY2FuZGlkYXRlLiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIHRoZSBjaXRhdGlvbiBudW1iZXJzIG9mIHRoZSBuIHBhcGVycywgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIEVhY2ggY2l0YXRpb24gbnVtYmVyIGlzIGFuIGludGVnZXIgYmV0d2VlbiAwIGFuZCAxMCwwMDAsIGluY2x1c2l2ZWx5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIHRoZSBpbnB1dC4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gYSBub24tbmVnYXRpdmUgaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIHEtaW5kZXguJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d