Merlin

Interview

Time limit2sMemory limit512 MB

Summary

Given n vessels with amounts of elixir, find the minimum number of vessels to empty (and smash) so the remaining vessels can be made equal by redistributing the poured elixir.

Level: Medium5 of 10
Topics: Greedy, Math, Sorting, Prefix sum
Solved: No attempts yet

Problem

One day, returning to his tower, Merlin found that Morgana had cursed all his vessels of the elixir of wisdom.

Merlin knows how to lift the curse, but the corresponding spell requires that all the vessels it is applied to hold an equal amount of elixir.

To achieve this, Merlin decided to act as follows. He chooses several vessels and pours all the elixir from the chosen vessels into the remaining ones. He may distribute the poured elixir among the remaining vessels arbitrarily. After all the elixir from the chosen vessels has been poured, Merlin smashes the emptied vessels (the curse can no longer be lifted from them), throws away the shards, and casts the curse-lifting spell on the remaining vessels.

Help the wizard find the smallest number of vessels he has to smash to lift Morgana's curse.

Input

The first line of the input file contains the number $n$ ( $2 \le n \le 10^5$ ), the number of vessels. The second line contains $n$ numbers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ), the number of liters of the elixir of wisdom in each vessel.

Output

Output the minimum number of vessels Merlin has to smash.

Notes

In the first example, for instance, one can pour $0.5$ liters of elixir from the first vessel into the second and $1.5$ liters into the third, then smash the first vessel.

In the second example, the vessels initially contain equal amounts of elixir, so nothing needs to be poured.

In the third example, for instance, one can pour 1 liter of elixir from the first vessel into the second, 2 liters each from the fifth vessel into the second and third, 1 liter from the fifth vessel into the fourth, then smash the first and fifth vessels.

Examples3

Example 1
Input
```
3
2 3 2
```
Expected output
```
1
```
Example 2
Input
```
4
4 4 4 4
```
Expected output
```
0
```
Example 3
Input
```
5
1 2 3 4 5
```
Expected output
```
2
```