Enlarge GCD

题目描述

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

样例 #2

样例输入

4
6 9 15 30

样例输出

2

样例 #3

样例输入

3
1 1 1

样例输出

-1

说明/提示

第一个示例： 初始最大公约数为 $1$。移除数字 $1$ 后，剩余数字的最大公约数可增大至 $2$。答案为 $1$。

第二个示例： 初始最大公约数为 $3$。移除 $6$ 和 $9$ 后，剩余数字的最大公约数可增大至 $15$。不存在只移除一个整数的方案，因此答案为 $2$。

第三个示例： 不存在能增大最大公约数的方案，因此答案为 $-1$。