AUCSE012 - Student Proxy

no tags 

 

There are N students in a class.
All the students have different expertise in giving proxies(I hope this term is clear).
Precisely, we associate an integer P with every student which denotes the number of proxies he can make. 
All students are capable of making proxies for any other student.A 

 

A Proxy in context of class attendance refers to the act when a student who is present in a class makes attendance for a student who is absent in the same class.

There are N students in a class.

All the students have different expertise in giving proxies.

Precisely, we associate an integer P with every student which denotes the number of proxies he can make. 

All students are capable of making proxies for any other student.

 

 

Input

 

First line contains an integer N(1 <= N <= 1000000) denoting the total number of students.

Then, N lines follow each containing an integer Ai(1 <= Ai <= 100). The integer Ai on the ith line denotes the number of proxies that the ith student can make.

 

Output

 

Print the minimum number of students that can be present in the class such that by giving proxies the recorded attendance can be 100%.

 

Example

Input:
5
1
3
2
1
2

Output:
2

Explanation, one possible solution is that the first and second student are present. Now first student can give 1 proxy and second can give 2 proxies making the recorded attendance 5.


hide comments
Francky: 2012-04-14 10:22:39

There is some Ai equal to 0.
It cost me some WA !!!
It's a real challenge in Python, reading in time is hard !

Nitin Sharma: 2012-04-14 10:22:39

should be moved to tutorial !!

Suraj D: 2012-04-14 10:22:39

tutorial for sure!!

Last edit: 2012-04-10 12:13:32

Added by:amit karmakar
Date:2011-08-06
Time limit:0.310s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All