畀定一個長度為 $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)$.