Se te da una secuencia de longitud $N$, $A = (A_1, A_2, \dots, A_N)$. Para esta secuencia $A$, realiza la siguiente operación en orden para $i = 1, 2, \dots, N - 1$:
- O bien intercambiar $A_i$ y $A_{i+1}$, o no hacer nada.
Encuentra el número de secuencias distintas que pueden resultar después de realizar estas operaciones, módulo $998244353$.
Entrada
La entrada se proporciona en el siguiente formato:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Todas las entradas son enteros.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Salida
Imprime la respuesta en una sola línea.
Ejemplos
Entrada 1
5 1 2 1 2 3
Salida 1
10
Entrada 2
9 3 1 6 2 2 7 7 6 6
Salida 2
104
Nota
En el primer ejemplo, hay $10$ secuencias posibles que pueden resultar después de realizar las operaciones. Estas secuencias son:
- $(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)$.