Problem Statement

For a tree $T$ with $N$ vertices called vertex $1$, vertex $2$, $\ldots$, vertex $N$, let $f(T)$ be the permutation $P$ of $(1,2,\ldots,N)$ obtained by the following procedure.

• Initially, let the sequence $P$ be the empty sequence $()$, and let the set $S$ be $\lbrace1\rbrace$.
• Repeat the following $N$ times.
• Let $x$ be the minimum value of $S$. Remove $x$ from $S$, and append $x$ to the end of $P$.
  • Then, let $v_1, v_2, \ldots, v_k$ be the vertices adjacent to vertex $x$ in $T$. For $i=1,2,\ldots,k$, if $v _ i$ is not contained in $P$, add $v _ i$ to $S$.

You are given a permutation $Q=(Q _ 1,Q _ 2,\ldots,Q _ N)$ of $(1,2,\ldots,N)$. Find the number, modulo $998244353$, of trees $T$ such that $f(T)=Q$. Here, two trees are distinguished when there exists a pair of vertices $(u,v)$ such that there is an edge between vertex $u$ and vertex $v$ in one tree and there is no edge in the other tree.

Constraints

• $1\le N\le2\times10 ^ 5$
• $1\le Q _ i\le N\ (1\le i\le N)$
• $Q _ i\ne Q _ j\ (1\le i\lt j\le N)$
• $Q _ 1=1$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
Q _ 1 Q _ 2 \ldots Q _ N

Output

Output the number, modulo $998244353$, of trees $T$ such that $f(T)=Q$.