One day, returning to his tower, Merlin discovered that Morgana had placed a curse on
all his vessels with the elixir of wisdom.
Merlin knows how to break the curse, but the corresponding spell requires everyone
the vessels to which it is applied had an equal amount of elixir.
To achieve this, Merlin decided to proceed as follows. It selects multiple
vessels and pours all the elixir from the selected vessels into the remaining ones. It can distribute
pourable elixir between the remaining vessels at random. After the whole
the elixir from the selected vessels is poured, Merlin breaks the empty vessels (curse from them
can no longer be removed), ejects shards and casts a remove curse spell on the remaining
vessels.
Help the wizard find out what is the least number of vessels he will have to break,
to break Morgana's curse.
Input data format
The first line of the input file contains the number n (2 ≤ n ≤ 105) — the number of vessels. Vo
the second line contains n integers a1, a2, . . . , an (1 ≤ ai ≤ 109) — number of liters of elixir
wisdom in every vessel.
Output Format
Print in the output file the minimum number of vessels that Merlin will have
smash.
Example
Input
3
2 3 2
Conclusion
1
Input:
4
4 4 4 4
Conclusion
0
Input
5
1 2 3 4 5
Conclusion
2
In the first example, you can, for example, pour 0.5 liters of elixir from the first vessel into the second one
and 1.5 liters into the third, after which break the first vessel.
In the second, the vessels initially contain an equal amount of elixir, you can not pour anything.
In the third example, you can, for example, pour 1 liter of elixir from the first vessel into the second one, by
2 liters from the fifth to the second and third, 1 liter from the fifth to the fourth, then split the first and
fifth vessels.