CF1909F2 Small Permutation Problem (Hard Version)

[Andy Tunstall - MiniBoss](https://soundcloud.com/tunners/miniboss) ⠀ 在简单版本中，$a_i$ 的取值范围为 $[0, n]$；在困难版本中，$a_i$ 的取值范围为 $[-1, n]$，且“好排列”的定义略有不同。只有当所有版本的问题都被解决时，你才能进行 hack。 给定一个整数 $n$ 和一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，其中每个 $a_i$ 的取值范围为 $[-1, n]$。 对于 $[1, 2, \dots, n]$ 的一个排列 $p_1, p_2, \dots, p_n$，如果对于每个 $i$，都满足以下条件，则称该排列为“好排列”： - 如果 $a_i \neq -1$，则在 $[p_1, p_2, \dots, p_i]$ 中小于等于 $i$ 的数的个数恰好为 $a_i$。 请你计算 $[1, 2, \dots, n]$ 的好排列的个数，答案对 $998\,244\,353$ 取模。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \le a_i \le n$），描述了好排列的条件。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行一个整数，表示好排列的数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，所有长度为 $5$ 的排列都是好排列，所以有 $120$ 个好排列。 在第二个测试用例中，唯一的好排列是 $[1, 2, 3, 4, 5]$。 在第三个测试用例中，有 $4$ 个好排列：$[2, 1, 5, 6, 3, 4]$，$[2, 1, 5, 6, 4, 3]$，$[2, 1, 6, 5, 3, 4]$，$[2, 1, 6, 5, 4, 3]$。例如，$[2, 1, 5, 6, 3, 4]$ 是好排列，因为： - $a_1 = 0$，在 $[p_1] = [2]$ 中小于等于 $1$ 的数有 $0$ 个； - $a_2 = 2$，在 $[p_1, p_2] = [2, 1]$ 中小于等于 $2$ 的数有 $2$ 个； - $a_3 = 2$，在 $[p_1, p_2, p_3] = [2, 1, 5]$ 中小于等于 $3$ 的数有 $2$ 个； - $a_4 = 2$，在 $[p_1, p_2, p_3, p_4] = [2, 1, 5, 6]$ 中小于等于 $4$ 的数有 $2$ 个； - $a_5 = -1$，因此 $[p_1, p_2, p_3, p_4, p_5]$ 没有限制； - $a_6 = -1$，因此 $[p_1, p_2, p_3, p_4, p_5, p_6]$ 没有限制。 由 ChatGPT 4.1 翻译