题目描述

定义一个长度为 $k$ 的数列的价值为：$val = \max \limits_{1 \le i \le k}\{i \times f(i,k)\}$。

其中 $f(i,j)$ 表示区间 $[i,j]$ 范围内数值种类数。

给出一个长度为 $n$ 的数列，计算所有连续子区间的价值总和。将一个连续子区间视为一个独立的数列，计算出的价值即为该连续子区间的价值。

设 $m$ 为数列里出现的数值种类数。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个正整数，$a_1, a_2, \dots, a_n$ 描述数列里每个位置上的数值。

对于所有的输入数据，都满足 $1\le n \le 10^5$。

输出格式

第一行输出一个整数表示答案对 $998\ 244\ 353$ 取模。

4
12 23 23 45

23

提示

【样例解释 1】

所有长度为 $1$ 的区间对答案的贡献都是 $1$。

所有长度为 $2$ 的区间对答案的贡献都是 $2$。

$[1,3]$ 这个区间对答案贡献为 $3$。

$[2,4]$ 这个区间对答案贡献为 $4$。

$[1,4]$ 这个区间对答案贡献为 $6$。

综上答案为 $ans = 4 \times 1 + 2 \times 3 + 3 + 4 + 6 = 23$。

【样例 2】

见题目附件 2.in/ans

【样例 3】

见题目附件 3.in/ans

【样例 4】

见题目附件 4.in/ans

【样例 5】

见题目附件 5.in/ans

【子任务】

子任务编号	$n\le$	$m\le$	$a_i\le$	约束	分值
1	$800$		$10^5$	无	13
2	$10^5$			不会出现相同的数值	15
3	$8\times 10^4$	$600$		$[1,m][m+1,2m]\dots[\lfloor\frac{n}{m}\rfloor\times m + 1,n]$每个区间无重复数值	21
4	$10^5$	$80$		无	24
5	$8\times 10^4$	$600$			27