小排列问题（困难版）

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定整数 $n$ 和长度为 $n$ 的数组 $a$，其中 $-1\le a_i\le n$。

对 $1,2,ldots,n$ 的一个排列 $p$，若对每个 $i$ 都满足：当 $a_i\ne-1$ 时，前缀 $p_1,ldots,p_i$ 中不超过 $i$ 的数恰好有 $a_i$ 个，则称 $p$ 是好排列。

求好排列的数量，答案对 $998244353$ 取模。

输入格式

第一行一个整数 $t$，表示测试数据组数。

每组数据的第一行一个整数 $n$，第二行为 $n$ 个整数 $a_1,ldots,a_n$。

输出格式

对每组数据输出一行一个整数，表示好排列数对 $998244353$ 取模的结果。

样例输入 1

3
5
-1 -1 -1 -1 -1
5
1 2 3 4 5
6
0 2 2 2 -1 -1

样例输出 1

120
1
4

数据范围

• $1\le t\le10^4$；
• $1\le n\le2\times10^5$；
• $-1\le a_i\le n$；
• 单个输入中所有测试数据的 $n$ 之和不超过 $2\times10^5$。

计分方式

本题按测试点独立计分，同一子任务中的测试点等分。