题目描述

给出由 $n$ 个数字组成的数列 $a_1,a_2,\cdots,a_n$，定义 $d(i,j)$ 为 $a_i$ 与 $a_j$ 之间的距离，即 $d(i,j) = |i-j|, (i \neq j)$。

现在需要你找出这个数列中距离最大的两个质数，求出最大的距离，如果不存在两个质数，输出 -1。

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

输入格式

第一行一个整数 $n$，表示有 $n$ 个数字。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示这个数列。

输出格式

一行一个整数，表示最大的距离。

样例数据

输入样例 #1

5
4 2 6 5 3

输出样例 #1

3

最远的两个质数是 $2$ 和 $3$，距离为 $3$。

输入样例 #2

5
1 2 4 6 8

输出样例 #2

-1

数据范围

对于 $10\%$ 的数据，$a_i = 2*i$；

对于 $80\%$ 的数据，$2 \le n \le 10^5$，$1 \le a_i \le 10^5$；

对于 $100\%$ 的数据，$2 \le n \le 10^6$，$1 \le a_i \le 10^5$ 。

备注：本题测试数据为民间数据