题目描述

有 $n$ 张扑克，第 $i$ 张扑克上写有一个正整数 $a_i$。

现在要把扑克划分成若干个合法的连续子段，其中，一个连续子段 $[l,r]$ “合法”当且仅当这个子段同时满足两个条件：

• $a_l< a_r$
• $\gcd(a_l,a_r)>1$

请问最多能划分多少段。如果没有合法的划分方案，输出 $-1$ 即可。

如果您不知道 $\gcd$ 是什么意思，请看“提示”部分。

输入格式

第一行一个整数 $n$。
第二行 $n$ 个整数表示序列 $a$。

输出格式

一个整数，如题目描述所示。

5
2 1 8 3 9

2

5
5 4 3 2 1

-1

20
20 9 36 36 40 8 3 10 9 20 18 12 30 20 30 15 8 9 27 45

7

提示

数据范围

本题采用捆绑测试。

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

样例解释

对于样例 $1$，有且仅有一种划分方案 $\{2,1,8\},\{3,9\}$。
对于样例 $2$，无合法的划分方案。

提示

对于两个正整数 $a,b$，$\gcd(a,b)$ 为它们的最大公因数，即满足既是 $a$ 的因数又是 $b$ 的因数的数中最大的数。