Сізге ұзындығы $N$ болатын $A = (A_1, A_2, \dots, A_N)$ тізбегі берілген. Осы $A$ тізбегі үшін $i = 1, 2, \dots, N - 1$ ретімен келесі операцияны орындаңыз:
- Не $A_i$ мен $A_{i+1}$ орындарын ауыстырыңыз, не ештеңе істемеңіз.
Осы операцияларды орындағаннан кейін пайда болуы мүмкін әртүрлі тізбектердің санын $998244353$ модулі бойынша табыңыз.
Кіріс деректері
Кіріс деректері келесі форматта беріледі:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Барлық кіріс деректері бүтін сандар болып табылады.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Шығыс деректері
Жауапты бір жолда шығарыңыз.
Мысалдар
Кіріс 1
5 1 2 1 2 3
Шығыс 1
10
Кіріс 2
9 3 1 6 2 2 7 7 6 6
Шығыс 2
104
Ескертпе
Бірінші мысалда операцияларды орындағаннан кейін шығуы мүмкін $10$ тізбек бар. Бұл тізбектер:
- $(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)$.