题目描述

長さ $N$ の整数列 $A_1,A_2,\cdots,A_N$ が与えられます．

$A$ の非空な部分列 $s$ であって，以下の条件を満たすものの個数を $998244353$ で割った余りを求めてください．

• $A$ から $s$ を取り出す方法が一意である． つまり，$s=(s_1,s_2,\cdots,s_k)$ とした時，$A_{idx(i)}=s_i$ ($1\ \leq\ i\ \leq\ k$)を満たす添字の列 $ 1\ \leq\ idx(1)\ <\ idx(2)\ <\ \cdots\ <\ idx(k)\ \leq\ N $ がちょうど一つ存在する．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

答えを出力せよ．

题目大意

给定长为 $n(n\le 2\times 10^5)$ 的数列 $a$，保证 $1\le a_i\le n$，求这个数列的非空、仅出现一次的子序列的个数 $\bmod 998244353$。

令构成子序列 $S$ 时选取的下标为 $s_1,\cdots,s_{k_1}$，构成子序列 $T$ 时所选取的下标为 $t_1,\cdots,t_{k_2}$，则在

$$\begin{cases}k_1=k_2\\\forall i\in[1,k_1],S_i=T_i\\\exists i\in[1,k_1],s_i\ne t_i\end{cases} $$

时，认为 $S$ 在 $a$ 中出现了不止一次。

3
1 2 1

5

4
4 2 1 3

15

12
1 2 3 6 9 2 3 3 9 6 1 6

1178

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ N$
• 入力される値はすべて整数である

Sample Explanation 1

以下の $5$ つの部分列が条件を満たします． - $(1,1)$ - $(1,2)$ - $(1,2,1)$ - $(2)$ - $(2,1)$ 部分列 $(1)$ は取り出す方法が $2$ 通りあるので条件を満たしません．