P7810 [JRKSJ R2] Upper

有 $n$ 张扑克，第 $i$ 张扑克上写有一个正整数 $a_i$。 现在要把扑克划分成若干个合法的连续子段，其中，一个连续子段 $[l,r]$ “合法”当且仅当这个子段同时满足两个条件： * $a_l< a_r$ * $\gcd(a_l,a_r)>1$ 请问最多能划分多少段。如果没有合法的划分方案，输出 $-1$ 即可。 如果您不知道 $\gcd$ 是什么意思，请看“提示”部分。

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

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

### 数据范围 本题采用捆绑测试。 对于 $100\%$ 的数据，$2\le n\le 10^5$，$1\le a_i\le 10^9$。 | $\text{Subtask}$ | $n\le$ | $a_i\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $10^9$ | 无 | $5$ | | $2$ | $3\times10^3$ | $10^9$ | 无 | $15$ | | $3$ | $2\times10^4$ | $10^6$ | 无 | $20$ | | $4$ | $2\times 10^4$ | $10^9$ | 无 | $10$ | | $5$ | $10^5$ | $10^9$ | 数据随机 | $10$ | | $6$ | $10^5$ | $10^9$ | 无 | $40$ | ### 样例解释 对于样例 $1$，有且仅有一种划分方案 $\{2,1,8\},\{3,9\}$。\ 对于样例 $2$，无合法的划分方案。 ### 提示 对于两个正整数 $a,b$，$\gcd(a,b)$ 为它们的最大公因数，即满足既是 $a$ 的因数又是 $b$ 的因数的数中最大的数。