问题描述

小核桃手里有一个数组 $a$，数组中恰好有 $n$ 个正整数 $a_1,a_2,...,a_n$。因为小核桃最近比较喜欢数字 $1$，所以他想把他手中的 $n$ 个数字全部变为 $1$。小核桃每次可以对数组 $a$ 执行这种操作：在数组 $a$ 中选择两个数字 $a_i, a_{i+1}（1 \le i\le n）$，然后将其中一个数字改为 $gcd$ ($a_i, a_{i+1}$)。

小核桃想要知道，他想要把所有的正整数全部变为 $1$，他至少需要执行几次操作？

输入描述

第一行是一个正整数 $n$，表示数组 $a$ 中正整数的数量。

第二行包含 $n$ 个用空格分开的正整数 $a_1, a_2, ..., a_n$。

输出描述

输出仅一行。

如果小核桃可以通过若干次操作，将所有的正整数全部变为 $1$，那么就输出他至少需要执行操作的次数。

如果小核桃无论如何都不能将所有的正整数全部变为 $1$，就输出“$No\ Way$”(不包含引号)。

4
2 4 6 8

No Way

5
2 2 3 4 6

5

样例解释

对于样例 $1$，小核桃没有办法把所有正整数全部变为 $1$.

对于样例 $2$, 小核桃可以通过下列五次操作将所有的正整数全部变为1：

$[2,2,3,4,6]->[2,1,3,4,6]->[2,1,3,1,6]->[1,1,3,1,6]->[1,1,1,1,6]->[1,1,1,1,1]$

数据范围与约定

对于所有的数据，均满足 $1 \leq a_i \leq 10^9$

大样例

大样例下载