تُعطى لك متتالية طولها $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)$.