P7810 [JRKSJ R2] Upper

There are $n$ poker cards. On the $i$-th card, there is a positive integer $a_i$. Now you need to divide the cards into several legal consecutive segments. A consecutive segment $[l,r]$ is “legal” if and only if it satisfies both conditions: * $a_l < a_r$. * $\gcd(a_l,a_r) > 1$. Ask for the maximum number of segments you can divide into. If there is no legal partition plan, output $-1$. If you do not know what $\gcd$ means, see the “Hint” section.

The first line contains an integer $n$.\ The second line contains $n$ integers representing the sequence $a$.

Output one integer, as described in the statement.

### Constraints This problem uses bundled testdata. For $100\%$ of the testdata, $2 \le n \le 10^5$, $1 \le a_i \le 10^9$. | $\text{Subtask}$ | $n\le$ | $a_i\le$ | Special property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $10^9$ | None | $5$ | | $2$ | $3\times10^3$ | $10^9$ | None | $15$ | | $3$ | $2\times10^4$ | $10^6$ | None | $20$ | | $4$ | $2\times 10^4$ | $10^9$ | None | $10$ | | $5$ | $10^5$ | $10^9$ | Random testdata | $10$ | | $6$ | $10^5$ | $10^9$ | None | $40$ | ### Sample Explanation For Sample $1$, there is one and only one partition plan: $\{2,1,8\},\{3,9\}$.\ For Sample $2$, there is no legal partition plan. ### Hint For two positive integers $a,b$, $\gcd(a,b)$ is their greatest common divisor, i.e. the largest number that is a divisor of both $a$ and $b$. Translated by ChatGPT 5