P15742 [JAG 2024 Summer Camp #2] Noncoprime Subsequences

Given a sequence $\boldsymbol{A} = (A_1, A_2, \ldots, A_N)$, a **good subsequence** of $\boldsymbol{A}$ is defined as a subsequence, that is not necessarily contiguous, where adjacent elements in the subsequence are not coprime. Find the maximum length $L$ of a good subsequence of $\boldsymbol{A}$. Also, determine the number of good subsequences of length $L$, modulo $998,244,353$.

The input is given in the following format: $$ \begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_N \end{aligned} $$ - $1 \leq N \leq 200,000$ - $1 \leq A_i \leq 10^6$ - All input values are integers.

Output 2 lines. On the first line, output $L$. On the second line, output the number of good subsequences of length $L$ of $\boldsymbol{A}$, modulo $998,244,353$.