CF2154F2.Bombing (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $n \le 10^6$. You can hack only if you solved all versions of this problem.

A permutation$^{\text{∗}}$ $b$ is considered a riffle shuffle of a permutation $a$ if $|a| = |b|$ and there exists $k$ where $1 \le k \lt |a|$ such that $a_1,a_2,\ldots,a_k$ and $a_{k + 1},a_{k + 2},\ldots,a_{|a|}$ are both subsequences$^{\text{†}}$ of $b$.

For example, $[\color{red}{1}, \color{blue}{4}, \color{blue}{5}, \color{red}{2}, \color{red}{3}, \color{blue}{6}]$ is a riffle shuffle of $[\color{red}{1}, \color{red}{2}, \color{red}{3}, \color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$ because we can select $k = 3$ and both $[\color{red}{1}, \color{red}{2}, \color{red}{3}]$ and $[\color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$ are subsequences.

You are given a permutation $p$ of length $n$ where some values are replaced with $-1$. Determine the number of ways to replace each $-1$ with an integer such that $p$ becomes a riffle shuffle of $[1,2,\ldots,n]$ (the sorted permutation).

The number of ways could be gargantuan, so output it modulo $998\,244\,353$.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

$^{\text{†}}$A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

这是该问题的困难版本。两个版本的区别在于，在本版本中，$n \le 10^6$。仅当您已解决该问题的所有版本时，才可进行 Hack。

若排列$^{\text{∗}}$ $b$ 满足 $|a| = |b|$，且存在整数 $k$（满足 $1 \le k \lt |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}]$ 的一次洗牌，因为可取 $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]$（即升序排列）的一次洗牌。

答案可能极大，请对 $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$ 中删除若干（可能为零个或全部）任意位置上的元素得到。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 10^6$) — the length of the permutation.

The second line of each test case contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le n$ or $p_i = -1$) — the elements of $p$. All elements of $p$ that are not $-1$ are distinct.

The sum of $n$ across all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 的 $p_i$ 均互不相同。

所有测试用例中 $n$ 的总和不超过 $10^6$。

For each testcase, output the number of ways to fill $p$ so that it is a riffle shuffle of $[1,2,\ldots,n]$ modulo $998\,244\,353$.

对于每个测试用例，输出满足条件的排列 $p$ 的个数（即 $p$ 是 $[1,2,\ldots,n]$ 的一次洗牌排列），结果对 $998\,244\,353$ 取模。

The possible permutations for the third test case are as follows:

• $[\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]$.

第三个测试用例的所有可能排列如下：

• $[\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]$。