题目描述

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

输入格式

第一行一个整数 $n$，

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

输出格式

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

3
1 2 4

1

4
6 9 15 30

2

样例1解释

删去 $1$ 这个数，最大公约数从 $1$ 变到 $2$。

样例2解释

删去 $6$、$9$，最大公约数从 $3$ 变到 $15$。

数据范围

对于 $30\%$ 的数据，$n \le 15$

对于 $50\%$ 的数据，$n,a_i \le 1000$

对于 $100\%$ 的数据，$n \le 300,000，a_i \le 1.5*10^7$