题目描述

给定一个长为 $n$ 的序列 $a\ (1\le a_i\le 1000)$，求 $\max\limits_{\gcd(a_i,a_j)=1}\{i+j\}$。换句话说，求 $i+j$ 的最大值，其中 $i,j$ 满足 $a_i$ 和 $a_j$ 互质。

输入格式

第一行输入一个数字 $n$

第二行输入 $n$ 个空格隔开的整数代表 $a_i$

输出格式

输出下标 $i+j$ 的最大值，若不存在两个下标 $i,j$ 满足题目给定的条件，输出 -1

3
3 2 1

5

7
1 3 5 2 4 7 7

12

3
2 2 4

-1

提示

第一个样例我们选择 $i=3,j=3$，这样两个数字都是 $1$，$1$ 和 $1$ 自己也是互质的，可以证明不存在别的答案。

对于第二个样例，选择 $i=7,j=5$，其中 $a_7,a_5$ 互质。

对于 $50\%$ 的数据，$2\leq n\leq 10^3$

对于 $100\%$ 的数据，$2\leq n\leq 2*10^5$