Statement

你有 $n$ 个分身， 还有 $n$ 个妹子。你所在的城市是的街区构成一个网格图，我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 个街区。其中第 $i(1\le i\le n)$ 个分身起点在 $(a_i,0)$，第 $i$ 个妹子终点在 $(i,0)$。

现在 $n$ 个妹子同时给你打电话，然而你想要调题于是让你的分身去见妹子。你的分身只能向又向下走，也即：每次只能从 $(i,j)$ 走到 $(i+1,j)$ 或者 $(i,j-1)$ 。如果两个分身走过了同一个街区（包括起点终点），则会有人同时看到两次一样的人，这样他会非常困扰，导致世界的运转收到阻碍。

你既不想让世界的运转受到阻碍，也不想鸽妹子。所以你想要知道满足每个分身路径不相交的方案数。两种方案不同当且仅当一个分身的路径不同。

对 $998244353$ 取模。

Task

input

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_i$ 表示第 $i$ 个起点的坐标。

output

一行一个整数表示答案。

Sample I

input

2
1 2

output

3

Constraints

对于 $100\%$ 的数据，$a_i\le a_{i+1}$, $n\le 5*10^5$，$0\le a_i< 10^6$。

$\textbf{subtask 1(15 pts)}$：$n\le 20$ 。

$\textbf{subtask 2(20 pts)}$：$n\le 500$。

$\textbf{subtask 3(15 pts)}$：$n\le 2000$。

$\textbf{subtask 4(30 pts)}$：$n\le 100000,a_i< 200000$。

$\textbf{subtask 4(20 pts)}$：无特殊限制。