408177: GYM103037 H Symphony

Salma is looking to create her new masterpiece symphony. She has created $$$10^{5}$$$ unique small pieces, each piece assigned a unique number between $$$1$$$ and $$$10^{5}$$$ respectively, to potentially use within the symphony (each piece takes the same amount of time to play). During one round of editing, she picked a non-empty subset of those pieces of size $$$n$$$ ($$$1 \leq n \leq 10^{5}$$$) that she wants to use in the symphony.

Now, given those $$$n$$$ pieces, she realized that the combination of those pieces, aka melodic sequence, that tends to sound the best follows the following rule:

• The pieces are played in strictly increasing order (so piece $$$4$$$ must be played before piece $$$5$$$ if both pieces are chosen for the sequence).
• If the sequence is of the form $$$x_1, x_2, \dots, x_k$$$ for some integer $$$k \geq 1$$$, it must be true that $$$\gcd(x_{i-1}, x_{i}) > 1$$$ for all integers $$$i$$$ satisfying $$$2 \leq i \leq k$$$.

Salma would like to make her symphony as long as possible so she would like given the $$$n$$$ pieces that she has picked, help her find the length of the longest melodic sequence (satisfying the conditions mentioned above) that she can make.

The input has two lines. The first line contains a single integer $$$n$$$ where $$$1 \leq n \leq 10^{5}$$$ and $$$n$$$ represents the number of pieces that Salma wants to pick from.

The second line of input will contain $$$n$$$ space separated integers $$$p_1, p_2, \dots, p_n$$$ where $$$1 \leq p_i \leq 10^{5}$$$, $$$p_{i} \neq p_{j}$$$ for all $$$i \neq j$$$, and $$$p_{i-1} < p_{i}$$$ for $$$2 \leq i \leq n$$$ (the integers will be unique and given in strictly ascending order).

Output a single integer representing the number of pieces in the longest melodic sequence you can make from the input.

5
2 3 4 7 9

2

9
1 2 3 5 6 7 8 9 10

4

In the first example, the longest melodic sequence is either [2, 4] or [6, 9] both of which have length 2. In the second example, some example melodic sequences are [2, 3, 6, 9] or [2, 6, 8] or [2, 6, 8, 10], and the longest one is of length 4.