Ti viene data una sequenza di lunghezza $N$, $A = (A_1, A_2, \dots, A_N)$. Per questa sequenza $A$, esegui la seguente operazione in ordine per $i = 1, 2, \dots, N - 1$:
- Scambia $A_i$ e $A_{i+1}$, oppure non fare nulla.
Trova il numero di sequenze distinte che possono risultare dopo aver eseguito queste operazioni, modulo $998244353$.
Input
L'input viene fornito nel seguente formato:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Tutti gli input sono interi.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Output
Stampa la risposta su una singola riga.
Esempi
Input 1
5 1 2 1 2 3
Output 1
10
Input 2
9 3 1 6 2 2 7 7 6 6
Output 2
104
Note
Nel primo esempio, ci sono $10$ possibili sequenze che possono risultare dopo aver eseguito le operazioni. Queste sequenze sono:
- $(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)$.