AT_abc468_e.Sum of Average

You are given a positive integer $N$ and a length-$N$ integer sequence $A=(A_1,A_2,\ldots,A_N)$.

Define $f(l,r)$ as the (arithmetic) mean of $A_l,A_{l+1},\ldots,A_r$.

Find $\displaystyle \sum_{1\le l\le r\le N} f(l,r)$, modulo $998244353$.

Definition of a rational number modulo $998244353$

Under the constraints of this problem, it can be proved that the rational number to be found is always an irreducible fraction $\frac{P}{Q}$ such that $Q {{}\not\equiv{}} 0 \pmod{998244353}$. Thus, there is a unique integer $R$ such that $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$. Output this $R$.

给定一个正整数 $N$ 和一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。

定义 $f(l,r)$ 为 $A_l,A_{l+1},\ldots,A_r$ 的（算术）平均值。

求 $\displaystyle \sum_{1\le l\le r\le N} f(l,r)$ 对 $998244353$ 取模的结果。

有理数对 $998244353$ 取模的定义

在本题的约束条件下，可以证明所求的有理数恒为一个既约分数 $\frac{P}{Q}$，且满足 $Q {{}\not\equiv{}} 0 \pmod{998244353}$。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出该 $R$。

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输入从标准输入中按以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output the answer.

输出答案。

Sample 1 Explanation:
We have $\displaystyle f(1,1)=2,f(1,2)=\frac{2+3}2=\frac52,f(2,2)=3$. Thus, $\displaystyle \sum_{1\le l\le r\le N} f(l,r)=2+\frac52+3=\frac{15}2$.

$\displaystyle \frac{15}2$ in modulo-$998244353$ expression is $499122184$, so output $499122184$.

Constraints

• $1\le N\le 5\times 10^5$
• $0\le A_i < 998244353$
• All input values are integers.

样例 1 解释：
我们有 $\displaystyle f(1,1)=2,f(1,2)=\frac{2+3}2=\frac52,f(2,2)=3$。因此，$\displaystyle \sum_{1\le l\le r\le N} f(l,r)=2+\frac52+3=\frac{15}2$。

$\displaystyle \frac{15}2$ 在模 $998244353$ 意义下的值为 $499122184$，故输出 $499122184$。

约束条件

• $1\le N\le 5\times 10^5$
• $0\le A_i < 998244353$
• 所有输入值均为整数。