问题 G: 最大公约数

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：10 通过：2

给定n个正整数，a_1,a_2,…,a_n,求最少删去几个数，使得删去后这些数的最大公约数比原先的所有数的最大公约数大。

第一行一个整数n，第二行n个正整数，a_1,a_2,…,a_n。

一个数，表示最少删去的个数，若无论怎么删都不会比原来的大，输出-1。

3
1 2 4

【输出输出样例1】

gcd.in

gcd.out

1 2 4

【样例1解释】
删去1这个数，最大公约数从1变到2。
【输出输出样例2】

gcd.in

gcd.out

6 9 15 30

【样例2解释】
删去6、9，最大公约数从3变到15
【数据范围】
对于30%的数据，n<=15
对于50%的数据，n,a_i<=1000
对于100%的数据，n<=300,000，a_i<=1.5*10^7