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

Bombing (Hard Version)

Examples