时空限制

2S/512M

题目描述

给定一个整数序列 $a$，$f(l,r)$ 定义为 $a_l , a _{l + 1} ,\cdots, a_{r}$ 中只出现奇数次的数字的和。 求

$$\big(\sum_{i = 1}^{n} \sum_{j = i}^{n} f(i,j) \big) \bmod 998244353 $$

格式

输入格式

第一行包含一个整数 $n$，表示序列 $a$ 的长度。

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

输出格式

输出一个整数，表示答案。

样例

样例输入 #1

3
1 2 1

样例输出 #1

12

样例解释 #1

区间 $[1,1]$：只包含 $1$，故 $f(1,1) = 1$。

区间 $[1,2]$：$1$ 出现 $1$ 次，$2$ 出现 $1$ 次，故 $f(1,2) = 3$。

区间 $[1,3]$：$1$ 出现 $2$ 次，$2$ 出现 $1$ 次，故 $f(1,3) = 2$。

区间 $[2,2]$：只包含 $2$，故 $f(2,2) = 2$。

区间 $[2,3]$：$1$ 出现 $1$ 次，$2$ 出现 $1$ 次，故 $f(2,3) = 3$。

区间 $[3,3]$：只包含 $1$，故 $f(3,3) = 1$。 故总和为 $1 + 3 + 2 + 2 + 3 + 1 = 12$。

样例输入 #2

10 
6 7 999 90 999 6 6 999 7 7

样例输出 #2

32766

数据规模

对于 $40\%$ 的数据 $1 \leq n \leq 1000, 1 \leq a_i \leq 10^6$。

对于 $60\%$ 的数据 $1 \leq n \leq 10^4,1 \leq a_i \leq 10^6$。

对于 $100\%$ 的数据 $1 \leq n \leq 5 \times 10^5, 1 \leq a_i \leq 10^9$。