P15742 [JAG 2024 Summer Camp #2] Noncoprime Subsequences

给定一个序列 $\boldsymbol{A} = (A_1, A_2, \ldots, A_N)$，定义 $\boldsymbol{A}$ 的一个**好子序列**为这样一个子序列（不要求连续），其中子序列内相邻的两个元素不互质。 求 $\boldsymbol{A}$ 的好子序列的最大可能长度 $L$。同时，求出长度为 $L$ 的好子序列的数量，结果对 $998,244,353$ 取模。

输入以如下格式给出： $$ \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$ - 所有输入值均为整数。

输出两行。第一行输出 $L$。第二行输出 $\boldsymbol{A}$ 中长度为 $L$ 的好子序列的数量，结果对 $998,244,353$ 取模。

翻译由 DeepSeek V3.2 完成