CF2154F2 Bombing (Hard Version)

这是该问题的难度较高版本。此版本与其他版本的区别在于本题中 $n \le 10^6$。只有在你解决了该问题所有版本后，才能进行 Hack。 若满足 $|a| = |b|$ 并存在 $k$，使得 $1 \le k < |a|$，并且 $a_1,a_2,\ldots,a_k$ 与 $a_{k + 1},a_{k + 2},\ldots,a_{|a|}$ 都是 $b$ 的子序列 $^{\text{†}}$，则称排列 $b$ 是排列 $a$ 的一次 riffle shuffle。 例如，$[\color{red}{1}, \color{blue}{4}, \color{blue}{5}, \color{red}{2}, \color{red}{3}, \color{blue}{6}]$ 是 $[\color{red}{1}, \color{red}{2}, \color{red}{3}, \color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$ 的一次 riffle shuffle，因为可以选 $k=3$，且 $[\color{red}{1}, \color{red}{2}, \color{red}{3}]$ 与 $[\color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$ 都是子序列。 你得到一个长度为 $n$ 的排列 $p$，其中某些值被替换成了 $-1$。请你计算将每个 $-1$ 替换为整数的方案数，使得 $p$ 变为 $[1,2,\ldots,n]$ （升序排列）的 riffle shuffle。 由于方案数可能非常大，请将结果对 $998\,244\,353$ 取模后输出。 $^{\text{∗}}$ 长度为 $n$ 的排列是 $1$ 到 $n$ 的 $n$ 个不同整数的任意排列。例如，$[2,3,1,5,4]$ 是排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$，但出现了 $4$）。 $^{\text{†}}$ 如果序列 $c$ 可以通过从序列 $d$ 中删除若干（可能为零或全部）任意位置的元素获得，则 $c$ 是 $d$ 的子序列。

每个测试点包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是具体的测试用例。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^6$）——排列的长度。 每个测试用例的第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$（$1 \le p_i \le n$ 或 $p_i = -1$），表示排列 $p$ 的元素。其中非 $-1$ 的元素互不相同。 所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出填充 $p$ 使其成为 $[1,2,\ldots,n]$ 的 riffle shuffle 的方案数，对 $998\,244\,353$ 取模。

第三个测试用例的所有可行排列如下： - $[\color{red}1, \color{blue}3, \color{blue}4, \color{red}2, \color{blue}5]$， - $[\color{red}1, \color{blue}4, \color{blue}5, \color{red}2, \color{red}3]$， - $[\color{blue}3, \color{red}1, \color{blue}4, \color{red}2, \color{blue}5]$， - $[\color{blue}3, \color{blue}4, \color{red}1, \color{red}2, \color{blue}5]$， - $[\color{blue}4, \color{red}1, \color{blue}5, \color{red}2, \color{red}3]$， - $[\color{blue}4, \color{blue}5, \color{red}1, \color{red}2, \color{red}3]$。 由 ChatGPT 5 翻译