题目描述

长度为 $N$ 的序列 $B=(B_1,\dots,B_N)$（每个元素为 $1$ 到 $N$ 之间的整数）被称为 好序列 当且仅当满足如下条件：

• 对于任意区间 $[l,r]$（$1\le l\le r\le N$），存在一个整数 $x$（$l\le x\le r$），使得满足下面的条件：

• • 先构造一个初始无边的图，顶点编号为 $1$ 到 $N$。对于每个 $i$ 满足 $l\le i\le r$ 且 $i\ne x$，向图中添加一条连接顶点 $i$ 和顶点 $B_i$ 的边。此时顶点 $l,l+1,\dots,r$ 在该图中构成一棵树（即这些顶点连通且恰有 $r-l$ 条边）。

现给定序列 $A=(A_1,\dots,A_N)$，其中每个元素要么是 $1$ 到 $N$ 之间的整数，要么是 $-1$。请统计将 $A$ 中的所有 $-1$ 元素替换为 $1$ 到 $N$ 之间整数的方案数，使得替换后的序列为一个 好序列。答案对 $998244353$ 取模。

输入格式

输入由标准输入给出，格式如下：

• 第一行一个正整数 $N$ 表示输入序列的长度；
• 第二行 $N$ 个由空格隔开的正整数，第 $i$ $(1 \le i \le N)$ 个正整数表示 $a_i$ 。

输出格式

输出一个整数，表示将 $A$ 中的 $-1$ 替换为 $1$ 到 $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 解释

样例 $1$ 中满足条件的替换共有 $7$ 种，列举如下：

$(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$：对 $i\in{1,2}$ 且 $i\ne x$，添加边 $(2,A_2)=(2,1)$，于是顶点 $1,2$ 连通且构成一棵树。其它区间也能验证成立，因此 $(1,1,2)$ 是好序列。

样例 2 解释

满足条件的替换为：

$(2,3,1)$、$(2,3,2)$、$(2,3,3)$。

数据范围

• 所有输入数均为整数。
• $1\le N\le 2\times 10^5$。
• $A_i\in{1,2,\dots,N}$ 或 $A_i=-1$。