At his birthday party, Sanjay the Koala wants to prepare a bowl of cookies for each of his ~N~ friends, filling ~N~ bowls with bags of Oreos. He realizes, however, that each Oreo bag has a different number of cookies, with the ~i~-th bag having ~a_i~ 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.

Constraints

For all subtasks:

~2 \le N \le 4 \cdot 10^3~

~1 \le a_i \le 10^9~

All ~a_i~ are distinct.

Subtask 1 [20%]

~2 \le N \le 200~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line of input will contain the integer ~N~.

The second line of input will contain ~N~ space-separated integers ~a_i~.

Output Specification

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

3

Explanation for Sample 1

We move ~2~ cookies from the third bowl into the second, resulting in ~3~ cookies in all three bowls.

Sample Input 2

4
1 2 6 5

Sample Output 2

2