CF1043F Make It One

Shirley 有一个数列 $\{a_i\}_{i=1} ^n$，她可以选出这些数中的任意多个元素（不必连续——原文为“subset子集”），然后得到等于这些数最大公因数的分数。 现在，她想要在得到 $1$ 分的前提下，使选择的数尽可能少，那么，她应该选择多少个数呢？ 如果任意选择都不能得到 $1$ 分，请输出 $-1$。

第一行：一个正整数 $n$。 第二行：$n$ 个正整数，给出了这个数列。

一行，如果任意选择都不能得到 $1$ 分，输出 $-1$。否则，输出选择元素的个数最小值。

$1\leq n\leq 300,000, \ 1\leq a_i \leq 300,000$