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

题目描述

Janusz is a businessman. He owns a company "Januszex", which produces games for teenagers. Last hit of Januszex was a cool one-person game "Make it one". The player is given a sequence of $ n $ integers $ a_i $ . It is allowed to select any subset of them, and the score is equal to the greatest common divisor of selected elements. The goal is to take as little elements as it is possible, getting the score $ 1 $ . Now Janusz wonders, for given sequence, how much elements should the player choose?

输入输出格式

输入格式

The first line contains an only integer $ n $ ( $ 1 \le n \le 300\,000 $ ) — the number of integers in the sequence. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 300\,000 $ ).

输出格式

If there is no subset of the given sequence with gcd equal to $ 1 $ , output -1. Otherwise, output exactly one integer — the size of the smallest subset with gcd equal to $ 1 $ .

输入输出样例

输入样例 #1

3
10 6 15

输出样例 #1

3

输入样例 #2

3
2 4 6

输出样例 #2

-1

输入样例 #3

7
30 60 21 42 70 15 30

输出样例 #3

3

说明

In the first example, selecting a subset of all numbers gives a gcd of $ 1 $ and for all smaller subsets the gcd is greater than $ 1 $ . In the second example, for all subsets of numbers the gcd is at least $ 2 $ .