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$.