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.

Input

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$.

Output

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$.

Note

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]$.