给你一个长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$。对于该序列 $A$，依次对 $i = 1, 2, \dots, N - 1$ 执行以下操作：

• 要么交换 $A_i$ 和 $A_{i+1}$，要么什么都不做。

求在执行完这些操作后，可能得到的不同序列的数量，对 $998244353$ 取模。

输入格式

输入格式如下：

$$ \begin{array}{l} N \\ A_1 \ A_2 \ \dots \ A_N \end{array} $$

数据范围

• 所有输入均为整数。
• $1 \le N \le 10^6$
• $1 \le A_i \le N$

输出格式

在一行中输出答案。

样例

输入样例 1

5
1 2 1 2 3

输出样例 1

10

输入样例 2

9
3 1 6 2 2 7 7 6 6

输出样例 2

104

说明

在第一个样例中，执行操作后可能得到的 $10$ 种不同序列如下：

• $(1,2,1,2,3)$
• $(1,2,1,3,2)$
• $(1,2,2,1,3)$
• $(1,2,2,3,1)$
• $(1,1,2,2,3)$
• $(1,1,2,3,2)$
• $(2,1,1,2,3)$
• $(2,1,1,3,2)$
• $(2,1,2,1,3)$
• $(2,1,2,3,1)$