Masala #F66VR4UQGX
Merlin
One day, returning to his tower, Merlin discovered that Morgana had put a curse on all his vessels with the elixir of wisdom. Merlin knows how to remove the curse, but the appropriate spell requires that all vessels to which it is applied have an equal amount of elixir. To achieve this, Merlin decided to act as follows. He selects several vessels and pours the entire elixir from the selected vessels into the remaining ones. He can distribute the transfused elixir between the remaining vessels in any way. After all the elixir has been removed from the selected vessels, Merlin breaks the emptied vessels (the curse can no longer be removed from them), throws out the fragments and applies a curse removal spell to the remaining vessels. Help the wizard find out what is the smallest number of vessels he will have to break in order to remove Morgana's curse.
The first line of the input file contains a number \(n (2 ≤ n ≤ 10^5 )\) —the number of vessels. The second line contains\(n\) numbers\(a_1, a_2, . . . , a_n (1 ≤ a_i ≤ 10^9 )\)— the number of liters of the elixir of wisdom in each vessel.
Output to the output file the minimum number of vessels that Merlin will have to break.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 2 3 2 |
1 |
| 2 |
4 4 4 4 4 |
0 |
| 3 |
5 1 2 3 4 5 |
2 |
In the first example, you can, for example, pour 0.5 liters of elixir from the first vessel into the second and 1.5 liters into the third, after which you 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, for example, you can pour 1 liter of elixir from the first vessel into the second, 2 liters each from the fifth into the second and third, 1 liter from the fifth into the fourth, and then break the first and fifth vessels.
Telegram kanalimizga obuna bo'ling