Anda diberikan sebuah barisan dengan panjang $N$, $A = (A_1, A_2, \dots, A_N)$. Untuk barisan $A$ ini, lakukan operasi berikut secara berurutan untuk $i = 1, 2, \dots, N - 1$:
- Tukar $A_i$ dan $A_{i+1}$, atau tidak melakukan apa-apa.
Temukan banyaknya barisan berbeda yang dapat dihasilkan setelah melakukan operasi-operasi ini, modulo $998244353$.
Masukan
Masukan diberikan dalam format berikut:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Semua masukan adalah bilangan bulat.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Keluaran
Cetak jawaban dalam satu baris.
Contoh
Masukan 1
5 1 2 1 2 3
Keluaran 1
10
Masukan 2
9 3 1 6 2 2 7 7 6 6
Keluaran 2
104
Catatan
Pada contoh pertama, terdapat $10$ kemungkinan barisan yang dapat dihasilkan setelah melakukan operasi-operasi tersebut. Barisan-barisan tersebut adalah:
- $(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)$.