P10342 [THUSC 2019] 数列

定义一个长度为 $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$ 取模。

**【样例解释 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$ | $800$ | $10^5$ | 无 | 13 | | 2 | $10^5$ | $10^5$ | $10^5$ | 不会出现相同的数值 | 15 | | 3 | $8\times 10^4$ | $600$ | $10^5$ | $[1,m][m+1,2m]\dots[\lfloor\frac{n}{m}\rfloor\times m + 1,n]$每个区间无重复数值 | 21 | | 4 | $10^5$ | $80$ | $10^5$ | 无 | 24 | | 5 | $8\times 10^4$ | $600$ | $10^5$| 无 | 27 |