题目描述

给定一个长度为 $N$ 的整数序列 $A_1,A_2,\cdots,A_N$。

请你求出 $A$ 的所有满足下述条件的非空子序列 $s$ 的个数，并对 $998244353$ 取模：

• 从 $A$ 中取出 $s$ 的方法是唯一的。也就是说，设 $s=(s_1,s_2,\cdots,s_k)$，存在且仅存在一组下标序列 $1 \leq idx(1) < idx(2) < \cdots < idx(k) \leq N$，使得 $A_{idx(i)}=s_i$ 对于 $1 \leq i \leq k$ 都成立。

输入格式

输入以如下格式从标准输入读入：

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

输出格式

请输出答案。

样例 1

输入

3
1 2 1

输出

5

样例 2

输入

4
4 2 1 3

输出

15

样例 3

输入

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$
• 输入的所有值均为整数。

样例解释 1

以下 $5$ 个子序列满足条件：

• $(1,1)$
• $(1,2)$
• $(1,2,1)$
• $(2)$
• $(2,1)$

子序列 $(1)$ 有 $2$ 种取法，因此不满足条件。

由 ChatGPT 4.1 翻译