Tree Sequence

时间限制：2s
空间限制：1024MB

题目描述

称一个长度为 $N$、元素均在 $1$ 到 $N$ 之间的整数序列 $B=(B_1,\ldots,B_N)$ 为好序列，当且仅当它满足下面的条件：

• 对每个区间 $[l,r]$，都存在一个 $x\in[l,r]$，使得按如下方式构造的图中，顶点 $l,l+1,\ldots,r$ 构成一棵树：先准备编号为 $1$ 到 $N$ 的 $N$ 个顶点；对每个 $i\in[l,r]$ 且 $i\ne x$，在顶点 $i$ 与顶点 $B_i$ 之间连边。

给定序列 $A=(A_1,\ldots,A_N)$，其中每个元素要么是 $1$ 到 $N$ 之间的整数，要么是 $-1$。求把每个 $-1$ 替换为 $1$ 到 $N$ 之间的整数，使 $A$ 成为好序列的方案数。答案对 $998244353$ 取模。

输入格式

第一行输入整数 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出合法替换方案数对 $998244353$ 取模后的结果。

样例输入 1

3
-1 -1 -1

样例输出 1

7

样例输入 2

3
-1 3 -1

样例输出 2

3

样例输入 3

6
2 3 -1 -1 -1 -1

样例输出 3

21

数据范围

• $1\le N\le 2\times 10^5$；
• $A_i=-1$ 或 $1\le A_i\le N$；
• 输入中的所有数均为整数。