A. Archmage's Crystals
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the high halls of Numeria, an archmage tends to $$$n$$$ magic crystals with powers $$$a_1, a_2, \ldots, a_n$$$. With a fusion spell, he may pick any two crystals with powers $$$x$$$ and $$$y$$$, remove them, and create a single crystal of power $$$x + y$$$. Each spell reduces the number of crystals by 1.

The archmage seeks harmony: he wants the average power of the crystals to become an integer. What is the minimum number of spells he must cast?

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^3$$$).

Output

Print a single integer: the minimum number of spells.

Examples
Input
4
5 2 3 5
Output
1
Input
5
11 12 13 14 15
Output
0
Input
4
1 5 3 7
Output
0
Note

A string $$$U$$$ is called a subsequence of a string $$$V$$$ if $$$U$$$ can be obtained from $$$V$$$ by deleting zero or more characters without changing the relative order of the remaining characters.