Вам дана последовательность длины $N$: $A = (A_1, A_2, \dots, A_N)$. Для этой последовательности $A$ выполните по порядку для $i = 1, 2, \dots, N - 1$ следующую операцию:
- Либо поменяйте местами $A_i$ и $A_{i+1}$, либо ничего не делайте.
Найдите количество различных последовательностей, которые могут получиться после выполнения этих операций, по модулю $998244353$.
Входные данные
Входные данные даны в следующем формате:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Все входные данные являются целыми числами.
- $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)$.