Sinulle annetaan pituutta $N$ oleva jono $A = (A_1, A_2, \dots, A_N)$. Suorita tälle jonolle $A$ seuraava operaatio järjestyksessä arvoille $i = 1, 2, \dots, N - 1$:
- Joko vaihda $A_i$ ja $A_{i+1}$ keskenään tai älä tee mitään.
Etsi niiden erilaisten jonojen lukumäärä, jotka voivat syntyä näiden operaatioiden suorittamisen jälkeen, modulo $998244353$.
Syöte
Syöte annetaan seuraavassa muodossa:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Kaikki syötteet ovat kokonaislukuja.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Tuloste
Tulosta vastaus yhdelle riville.
Esimerkit
Syöte 1
5 1 2 1 2 3
Tuloste 1
10
Syöte 2
9 3 1 6 2 2 7 7 6 6
Tuloste 2
104
Huomautus
Ensimmäisessä esimerkissä on $10$ mahdollista jonoa, jotka voivat syntyä operaatioiden suorittamisen jälkeen. Nämä jonot ovat:
- $(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)$.