Bạn được cho một dãy độ dài $N$, $A = (A_1, A_2, \dots, A_N)$. Đối với dãy $A$ này, hãy thực hiện thao tác sau theo thứ tự với $i = 1, 2, \dots, N - 1$:
- Hoặc đổi chỗ $A_i$ và $A_{i+1}$, hoặc không làm gì cả.
Hãy tìm số lượng dãy phân biệt có thể thu được sau khi thực hiện các thao tác này, theo modulo $998244353$.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- Tất cả dữ liệu vào đều là số nguyên.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
Kết quả
In ra câu trả lời trên một dòng duy nhất.
Ví dụ
Dữ liệu vào 1
5 1 2 1 2 3
Kết quả 1
10
Dữ liệu vào 2
9 3 1 6 2 2 7 7 6 6
Kết quả 2
104
Giải thích
Trong ví dụ thứ nhất, có $10$ dãy có thể thu được sau khi thực hiện các thao tác. Các dãy đó là:
- $(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)$.