AT_arc206_c [ARC206C] Tree Sequence

长度为 $N$ 的整数序列 $B = (B_1, \ldots, B_N)$，其中每个元素 $B_i$ 满足 $1 \leq B_i \leq N$，被称为好序列，当且仅当它满足以下条件： - 对于每一个区间 $[l, r]$（$1 \leq l \leq r \leq N$），存在一个整数 $x$（$l \leq x \leq r$），使得以下条件成立： - 准备一个包含 $N$ 个顶点（从 $1$ 到 $N$ 编号）、没有边的图。对于每一个 $l \leq i \leq r$，如果 $i \neq x$，就在顶点 $i$ 和顶点 $B_i$ 之间连一条边。此时，顶点 $l, l+1, \ldots, r$ 构成一棵树。即这些顶点是连通的。 给定一个长度为 $N$ 的序列 $A = (A_1, \ldots, A_N)$，其中每个元素要么是 $1$ 到 $N$ 之间的整数，要么是 $-1$。请你计算，有多少种方法可以将 $A$ 中所有的 $-1$ 替换为 $1$ 到 $N$ 之间的整数，使得序列 $A$ 成为一个好序列。答案对 $998244353$ 取模。

输入为标准输入，格式如下： > $N$ $A_1$ $\cdots$ $A_N$

输出一个整数，表示有多少种不同的替换方式使序列 $A$ 成为好序列，结果对 $998244353$ 取模。

### 样例解释 1 满足题目条件的替换有如下七种： - $(1,1,2)$ - $(2,1,2)$ - $(2,2,2)$ - $(2,3,1)$ - $(2,3,2)$ - $(2,3,3)$ - $(3,1,2)$ 以 $A=(1,1,2)$ 为例，区间 $[1,2]$ 可以通过选取 $x=1$ 来验证。此时连接了顶点 $2$ 和 $A_2=1$，顶点 $1,2$ 形成一棵树。 其余区间 $[1,1]$、$[2,2]$、$[3,3]$、$[2,3]$、$[1,3]$ 也都能满足条件，所以 $(1,1,2)$ 为好序列。 ### 样例解释 2 满足条件的替换有如下三种： - $(2,3,1)$ - $(2,3,2)$ - $(2,3,3)$ ### 数据范围 - 所有输入值均为整数。 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq A_i \leq N$ 或 $A_i = -1$。 由 ChatGPT 5 翻译