Du får en talföljd av längd $N$, $A = (A_1, A_2, \dots, A_N)$. För denna talföljd $A$, utför följande operation i ordning för $i = 1, 2, \dots, N - 1$:
- Byt antingen plats på $A_i$ och $A_{i+1}$, eller gör ingenting.
Hitta antalet distinkta talföljder som kan uppstå efter att dessa operationer har utförts, modulo $998244353$.
Indata
Indatan ges i följande format:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Alla indata är heltal.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Utdata
Skriv ut svaret på en enda rad.
Exempel
Indata 1
5 1 2 1 2 3
Utdata 1
10
Indata 2
9 3 1 6 2 2 7 7 6 6
Utdata 2
104
Förklaring
I det första exemplet finns det $10$ möjliga talföljder som kan uppstå efter att operationerna har utförts. Dessa talföljder är:
- $(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)$.