题目描述
Problem Description
There are $n$ poker cards, each card has a positive integer $a_i$ written on it.
You need to divide these cards into several valid continuous segments. A continuous segment $[l, r]$ is considered "valid" if and only if it satisfies both of the following conditions:
- $a_l < a_r$
- $\gcd(a_l, a_r) > 1$
Determine the maximum number of segments that can be formed. If there is no valid way to divide the cards, output $-1$.
If you are unfamiliar with the concept of $\gcd$, please refer to the "Hints" section.
Input Format
The first line contains an integer $n$.
The second line contains $n$ integers representing the sequence $a$.
Output Format
Output a single integer as described in the problem statement.
Sample Input and Output
Sample Input #1
5
2 1 8 3 9
Sample Output #1
2
Sample Input #2
5
5 4 3 2 1
Sample Output #2
-1
Sample Input #3
20
20 9 36 36 40 8 3 10 9 20 18 12 30 20 30 15 8 9 27 45
Sample Output #3
7
Notes
Data Range
This problem uses batched testing.
For $100\%$ of the data, $2 \le n \le 10^5$, $1 \le a_i \le 10^9$.
| Subtask | $n \le$ | $a_i \le$ | Special Conditions | Score |
|---|---|---|---|---|
| 1 | 5 | $10^9$ | None | 5 |
| 2 | $3 \times 10^3$ | $10^9$ | None | 15 |
| 3 | $2 \times 10^4$ | $10^6$ | None | 20 |
| 4 | $2 \times 10^4$ | $10^9$ | None | 10 |
| 5 | $10^5$ | $10^9$ | Data is random | 10 |
| 6 | $10^5$ | $10^9$ | None | 40 |
Sample Explanation
For Sample #1, the only valid division is $\{2, 1, 8\}, \{3, 9\}$.
For Sample #2, there are no valid divisions.
Hints
For two positive integers $a$ and $b$, $\gcd(a, b)$ represents their greatest common divisor, which is the largest number that divides both $a$ and $b$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分