BOPERISH - E - Publish of Perish

no tags 

“Publish or perish” is the academic life’s fundamental motto. It refers to the fact that publishing your work frequently is the only way to guarantee access to research funds, bright students and career advances. But publishing is not enough. It is necessary that your work is referenced (or cited). That is, your papers must be mentioned as source of information in other people’s publications, to attest the quality and relevance of your research. The more citations a paper receives from other authors, the more it is considered influential.

In 2005 Jorge E. Hirsch, a physicist at the University of California at San Diego, proposed a way to evaluate the scientific impact of a researcher, based on the citations his or her papers have received. The h-index, as Hirsch’s proposal became known, is a number based on the set of a researcher’s most cited papers. It is defined in Hirsch’s own words as: A scientist has index h if h of his Np papers have at least h citations each, and the other (Np − h) papers have at most h citations each.

Albert Einstein, for example, published 319 papers in scientific journals and has an h-index equal to 46. It means 46 of his papers have received 46 or more citations each, and all of his remaining 273 papers have 46 citations or less each. Given the information of how many citations each paper from a given researcher has received, write a program to calculate that researcher’s h-index.

Input

The input contains several test cases. The first line of a test case contains one integer N indicating the number of papers a researcher has published (1<=N<=103). The second line contains a list of N integers Mi, separated by one space, representing the number of citations each of the N papers from that author has received (0<=Mi <=103, for 1<= i <= N). The end of input is indicated by a line containing only one zero.

Output

For each test case in the input, your program must print a single line, containing one single integer, the h-index for the given list of citations.

Sample Input

4
1003 1 200 2
10
1 1 1 0 1 1 0 1 1 1
7
6 5 4 3 2 1 0
0

Sample Output

2
1
3

hide comments
nadstratosfer: 2018-10-26 02:09:36

0 <= Mi <= 1003 but if that matters to your code, you're not doing it right.

xceptor: 2015-09-11 18:11:19

Time wasting Que.

Ruffneck: 2015-06-19 17:11:52

constraints unreliable,
take care of test cases like:
3
0 0 0

rahul kumar singh: 2013-07-09 13:12:56

short n simple

Dheeraj Kumar: 2013-07-08 12:42:15

Nice question.Has a good thinking part. :)
AC in first go.

a b : 2013-02-13 20:48:00

ahhh... uselessly spent so much time

Mukul: 2012-10-01 10:28:12

finally ac :)

Last edit: 2012-10-01 10:58:32
:::x:::: 2010-12-15 08:00:58

i think Mi is not <=1000
please update problem statement

:D: 2010-07-11 21:29:52

Checked limits: N<=2^10, -2^20<=Mi<=2^20

Kumar Anurag: 2010-06-22 21:01:35

The H-index >=0 .
Not considering for "0" may give WA.


Added by:Alvaro Javier Medina Balboa
Date:2010-05-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA