Problem Description

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.

Input Format

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

Output Format

Output one integer, as described in the statement.

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

Hint

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $2 \le n \le 10^5$, $1 \le a_i \le 10^9$.

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