Sum of Averages (subarray)

2 secs 1024 MB
yunipoke's icon yunipoke

問題文

長さNNの数列AAが与えられます。AAの空でない連続部分列はN(N+1)2\frac{N(N+1)}{2}通りありますが、それぞれについて値の平均を計算し、それらの総和をmod998244353mod998244353で求めてください。

制約

  • 1N2×1051 \leq N \leq 2 \times10^5
  • 1Ai1091 \leq A_{i} \leq 10^9

入力

入力はすべて整数である。

N
A_1 A_2 ... A_N

出力

計算結果を一行に出力せよ。

サンプル

入力1
3
1 2 3
出力1
12

AAの空でない連続部分列は{1}\{1\},{2}\{2\},{3}\{3\},{1,2}\{1,2\},{2,3}\{2,3\},{1,2,3}\{1,2,3\}の6つです。 値の平均はそれぞれ11,22,33,32\frac{3}{2},52\frac{5}{2},22です。これらの総和である12が答えとなります。

入力2
5
10 2 3 6 4
出力2
70
入力3
15
611609221 130604016 908556959 572844438 421449617 876143797 451739574 696504047 748732603 977231473 518897757 385226840 772638935 726395840 625232881
出力3
275568151

提出


Go (1.21)