問題文

正整数 N と、長さ N の整数列 A が与えられます。

1 \le l \le r \le N を満たすすべての整数対 (l, r) について \displaystyle \left | \sum_{k=l}^{r} A_k \right | を求め、それらの和を 998244353 で割った余りを出力してください。

制約

• 1 \le N \le 2 \times 10^5
• |A_i| \le 10^9 \ (1 \le i \le N)
• 入力は全て整数

入力例 1

3
1 -2 3

出力例 1

10

|1| + |1 + (-2)| + |1 + (-2) + 3| + |(-2)| + |(-2) + 3| + |3| = 1 + 1 + 2 + 2 + 1 + 3 = 10 です。

入力例 2

2
-1 1

出力例 2

2

入力例 3

4
314159265 358979323 846264338 327950288

出力例 3

815701001

998244353 で割った余りを出力することをお忘れなく。

原案: Chippppp