At his birthday party, Sanjay the Koala wants to prepare a bowl of cookies for each of his friends, filling bowls with bags of Oreos. He realizes, however, that each Oreo bag has a different number of cookies, with the -th bag having cookies. Sanjay wants everyone to have the same number of cookies, but as his friends are calling him back, he only has time to take a number of cookies from a single bowl and place all of the cookies he took into another bowl. Given this constraint, Sanjay wants to know the maximum number of bowls he can have with an identical number of cookies! Can you help him?
For this problem, Python users are recommended to use PyPy over CPython.
For all subtasks:
All are distinct.
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
The first line of input will contain the integer .
The second line of input will contain space-separated integers .
Output the maximum number of bowls with an identical number of cookies that Sanjay can obtain.
Sample Input 1
3 3 1 5
Sample Output 1
Explanation for Sample 1
We move cookies from the third bowl into the second, resulting in cookies in all three bowls.
Sample Input 2
4 1 2 6 5
Sample Output 2