时空限制

1S/512M

题目描述

给出一个长度为 $n$ 的数组 $a$。

设 $S$ 为 $a$ 的所有不同的、非空子序列的集合。两个子序列被视为是相同的，当且仅当它们对应的元素序列完全相同（即按值去重，即使它们在原数组中的下标选择不同，只要值相同就只保留一个）。

对于两个序列 $u$ 和 $v$，我们定义 $\text{lcp}(u, v)$ 为它们的最长公共前缀的长度。

请你计算以下式子的值：

$$\sum_{u \in S} \sum_{v \in S} \text{lcp}(u, v)$$

由于答案可能很大，请输出其对 $998244353$ 取模后的结果。

格式

输入格式

第一行包含一个正整数 $n$，表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组的元素。

输出格式

输出一个整数，表示答案对 $998244353$ 取模后的结果。

样例

样例输入 #1

3
1 2 1

样例输出 #1

27

样例解释 #1

数组 $[1, 2, 1]$ 的所有不同的非空子序列为：

$$[1],[2],[1, 2],[1, 1],[2, 1],[1, 2, 1]$$

以下是所有有序二元组 $(u, v)$，$\operatorname{lcp}(u, v)$ 对应的值的表格：

$u$ \ $v$	$[1]$	$[2]$	$[1,2]$	$[1,1]$	$[2,1]$	$[1,2,1]$
$[1]$	$1$	$0$	$1$	$1$	$0$	$1$
$[2]$	$0$	$1$	$0$	$0$	$1$	$0$
$[1,2]$	$1$	$0$	$2$	$1$	$0$	$2$
$[1,1]$	$1$	$0$	$1$	$2$	$0$	$1$
$[2,1]$	$0$	$1$	$0$	$0$	$2$	$0$
$[1,2,1]$	$1$	$0$	$2$	$1$	$0$	$3$

求和后答案为 $27$。

样例输入 #2

2
1 1

样例输出 #2

5

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$10$	$10$
$2$	$30$	$1000$
$3$	$60$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \leq a_i \leq n$。