Gegeben ist eine Folge der Länge $N$, $A = (A_1, A_2, \dots, A_N)$. Führe für diese Folge $A$ der Reihe nach für $i = 1, 2, \dots, N - 1$ die folgende Operation aus:
- Vertausche entweder $A_i$ und $A_{i+1}$, oder tue nichts.
Bestimme die Anzahl der verschiedenen Folgen, die nach dem Ausführen dieser Operationen entstehen können, modulo $998244353$.
Eingabe
Die Eingabe erfolgt im folgenden Format:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Alle Eingaben sind ganze Zahlen.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Ausgabe
Gib die Antwort in einer einzigen Zeile aus.
Beispiele
Eingabe 1
5 1 2 1 2 3
Ausgabe 1
10
Eingabe 2
9 3 1 6 2 2 7 7 6 6
Ausgabe 2
104
Hinweis
Im ersten Beispiel gibt es $10$ mögliche Folgen, die nach dem Ausführen der Operationen entstehen können. Diese Folgen sind:
- $(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)$.