Вам дано послідовність довжини $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)$.