F 先生有 $$$n$$$ 个正整数,$$$a_1, a_2, \ldots, a_n$$$。
他认为这些整数的最大公约数太小。所以他想通过去掉一些整数来扩大它。
但这道题对他来说太简单了,所以他不想自己做。如果你帮助他,他会给你一些分数作为奖励。
你的任务是计算需要删除的最小整数数,以使剩余整数的最大公约数大于所有整数的最大公约数。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — F 先生拥有的整数个数。
第二行包含 $$$n$$$ 整数,$$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 1.5 \cdot 10^7$$$)。
输出
打印一个整数 - 您需要删除的最小整数数,以便剩余整数的最大公约数大于所有整数的最大公约数。
您不应删除所有整数。
如果没有解决方案,则打印“-1”(不带引号)。
示例
输入 #1
3 1 2 4
输出 #1
1
输入 #2
4 6 9 15 30
输出 #2
2
输入 #3
3 1 1 1
输出 #3
-1
注意
在第一个示例中,最大公约数开头为 $$$1$$$。您可以删除$$$1$$$,以便最大公约数放大为$$$2$$$。答案是$$$1$$$。
在第二个示例中,最大公约数开头为 $$$3$$$。您可以删除 $$$6$$$ 和 $$$9$$$,以便将最大公约数放大为 $$$15$$$。没有一种解决方案只能删除一个整数。所以答案是$$$2$$$。
在第三个例子中,没有办法放大最大公约数。所以答案是$$$-1$$$。