题目描述

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

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

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

请计算：

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

输入格式

第一行包含一个正整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

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

3
1 2 1

27

样例 1 解释

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

枚举所有有序二元组 $(u,v)$ 后，$\operatorname{lcp}(u,v)$ 的总和为 $27$。

2
1 1

5

数据范围

对于全部数据，$1\le n\le 2\times 10^5$，$1\le a_i\le n$。