P12674 「LAOI-8」Count

给定一个长度为 $n$ 的序列 $A$，现在你需要将这个序列划分为若干个区间（可以只划分为一个），要求每个区间的左端点 $l$ 和右端点 $r$ 都满足 $A_l=A_r$，其中 $l$ 可以等于 $r$。 令这样一种合法划分的贡献为**所有非空区间内元素的乘积**之和（若区间内只有一个元素，那么认为这个区间内元素的乘积为这个元素的值）。 求所有合法划分的贡献之和对 $998244353$ 取模的值。

共两行。 第一行一个正整数 $n$，表示序列长度。 第二行 $n$ 个正整数，表示序列 $A$。

共一行一个整数，表示所有合法划分的贡献之和对 $998244353$ 取模的值。

### 样例解释 对于样例一中的序列 $\langle1,2,2,1\rangle$ 共存在三种合法划分： - 划分为 $4$ 个区间，分别为 $[1,1]$、$[2,2]$、$[3,3]$、$[4,4]$，贡献为 $1+2+2+1=6$。 - 划分为 $3$ 个区间，分别为 $[1,1]$、$[2,3]$、$[4,4]$，贡献为 $1+2\times2+1=6$。 - 划分为 $1$ 个区间，为 $[1,4]$，贡献为 $1\times2\times2\times1=4$。 所以总贡献的和为 $6+6+4=16$。 ### 数据范围 **本题采用捆绑测试。** |子任务编号|$n$|$A_i$|分值| |:-:|:-:|:-:|:-:| |$1$|$\le10$|$\le3$|$10$| |$2$|$\le10^3$|$\le40$|$20$| |$3$|$\le2.5\times10^5$|$\le2$|$30$| |$4$|$\le2.5\times10^5$|$\le40$|$40$| 对于 $100\%$ 的数据，保证 $1\le n\le2.5\times10^5$，$1\le A_i\le40$。