Du får oppgitt en følge med lengde $N$, $A = (A_1, A_2, \dots, A_N)$. For denne følgen $A$, utfør følgende operasjon i rekkefølge for $i = 1, 2, \dots, N - 1$:
- Enten bytt plass på $A_i$ og $A_{i+1}$, eller gjør ingenting.
Finn antallet distinkte følger som kan oppstå etter å ha utført disse operasjonene, modulo $998244353$.
Inndata
Inndataene gis på følgende format:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Alle inndata er heltall.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Utdata
Skriv ut svaret på én enkelt linje.
Eksempler
Inndata 1
5 1 2 1 2 3
Utdata 1
10
Inndata 2
9 3 1 6 2 2 7 7 6 6
Utdata 2
104
Forklaring
I det første eksempelet er det $10$ mulige følger som kan oppstå etter å ha utført operasjonene. Disse følgene er:
- $(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)$.