随机栈

题目描述

Toxel 获得了一个随机的 “栈”。这个栈可被视为一个多重集 $S$，从一个非空的随机栈 $S$ 中取出一个元素时，有可能从中取出任何一个元素，其中每个元素被取出的概率是相等的。取出该元素后，该元素会从集合中删除。以 $\{1, 2, 2\}$ 为例，有 $\frac{1}{3}$ 的概率取出 $1$，使得集合变为 $\{2, 2\}$，有 $\frac{2}{3}$ 的概率取出 $2$，使得集合变为 $\{1, 2\}$。每次取出元素的事件相互独立。

Toxel 正在对这个集合做一些操作。集合初始时为空，它总共进行了 $2n$ 次操作，其中 $n$ 次操作为插入，$n$ 次操作为取出。现在，Toxel 告诉了你它操作的顺序以及每次插入的数，且保证每次取出时，集合非空。Toxel 想知道，如果把每次取出的数排成一个序列，那么这个序列递增的概率是多少？

这里，递增的严格定义是：取出数列的每一项（除最后一项）小于等于它的后一项。

由于答案可能不是整数，为了方便计算，你只需要求出这个值对 $998 244 353$ 取模的结果。

输入格式

第一行包含一个整数 $n（1 ≤ n ≤ 2 × 10^5）$。 第二行包含 $2n$ 个整数 $a_1, a_2, . . . , a_{2n}（−1 ≤ a_i ≤ n）$，表示 Toxel 操作的序列。其中，若 $0 ≤ a_i ≤ n$，表示 Toxel 向集合中插入了 $a_i$；否则 $a_i = −1$，表示 Toxel 从集合中取出了一个元素。数据保证取出元素时，集合非空；保证插入和取出操作的次数分别为 $n$。

输出格式

输出一行一个整数，表示答案对 $998 244 353$ 取模的结果。

样例 #1

样例输入 #1

2
1 2 -1 -1

样例输出 #1

499122177

提示

正式地说，答案对 $998 244 353$ 取模表达了如下含义。令 $M = 998 244 353$，可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 均为整数，且 $q \not \equiv 0(\mod M)$。你需要输出 $p · q^{−1} \mod M$。换句话说，你需要输出满足 $0 ≤ x < M$ 且 $x · q ≡ p (mod M)$ 的整数 $x$。 对于样例一，可能有以下两种情况：

• 加入 $1$ 后，集合变成 $\{1\}$，加入 $2$ 后，集合变成 $\{1, 2\}$。接下来先取出 $1$，这里有 $\frac{1}{2}$ 的概率，接下来再取出 $2$。这种情况下，取出的序列为 $1, 2$，是递增的，概率为 $\frac{1}{2}$。
• 加入 $1$ 后，集合变成 $\{1\}$，加入 $2$ 后，集合变成 $\{1, 2\}$。接下来先取出 $2$，这里有 $\frac{1}{2}$ 的概率，接下来再取出 $1$。这种情况下，取出的序列为 $2, 1$，不是递增的，概率为 $\frac{1}{2}$。

有序的概率为 $\frac{1}{2}$，而 $2 · 499 122 177 ≡ 1 (\mod 998 244 353)$，故答案为 $499 122 177$。

对于样例二，$2$ 无论如何都会在第二个 $1$ 前被取出，递增的概率为 $0$。

对于样例三，取出的序列只有 $1, 2, 3, 4$ 一种情况，递增的概率为 $1$。