题目描述

给定一个长度为 $n$ 的序列 $A$，现在你需要将这个序列划分为若干个区间（可以只划分为一个），要求每个区间的左端点 $l$ 和右端点 $r$ 都满足 $A_l=A_r$，其中 $l$ 可以等于 $r$。

令这样一种合法划分的贡献为所有非空区间内元素的乘积之和（若区间内只有一个元素，那么认为这个区间内元素的乘积为这个元素的值）。

求所有合法划分的贡献之和对 $998244353$ 取模的值。

输入格式

共两行。

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

第二行 $n$ 个正整数，表示序列 $A$。

输出格式

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

4
1 2 2 1

16

6
1 2 2 1 2 2

104

提示

样例解释

对于样例一中的序列 $\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$。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1\le n\le2.5\times10^5$，$1\le A_i\le40$。