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

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

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

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