配点 : $500$ 点

問題文

カード $1$, カード $2$, $\ldots$, カード $N$ の $N$ 枚のカードがあり、 カード $i$ $(1\leq i\leq N)$ には整数 $A_i$ が書かれています。

$K=1,2,\ldots,N$ について、次の問題を解いてください。

カード $1$, カード $2$, $\ldots$, カード $K$ の $K$ 枚のカードが入っている袋があります。 次の操作を $2$ 回繰り返し、記録された数を順に $x,y$ とします。

袋から無作為にカードを $1$ 枚取り出し、カードに書かれている数を記録する。その後、カードを 袋の中に戻す 。

$\max(x,y)$ の値の期待値を $\text{mod} 998244353$ で出力してください（注記参照）。 ただし、$\max(x,y)$ で $x$ と $y$ のうち小さくない方の値を表します。

注記

求める期待値は必ず有限値かつ有理数となることが証明できます。また、この問題の制約下では、その値を互いに素な $2$ つの整数 $P$, $Q$ を用いて $\frac{P}{Q}$ と表したとき、$R \times Q \equiv P\pmod{998244353}$ かつ $0 \leq R \lt 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を出力してください。

制約

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 2\times 10^5$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

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

出力

$N$ 行出力せよ。 $i$ 行目 $(1\leq i\leq N)$ には、$K=i$ の時の問題に対する答えを出力せよ。

3
5 7 5

5
499122183
443664163

例えば、$K=2$ の時の答えは次のようにして求まります。

袋の中にはカード $1$ とカード $2$ が入っており、それぞれには $A_1=5$ と $A_2=7$ が書かれています。

• $1$ 回目に取り出されたカードがカード $1$ 、$2$ 回目に取り出されたカードもカード $1$ のとき、$x=y=5$ であり、$\max(x,y)=5$ となります。
• $1$ 回目に取り出されたカードがカード $1$ 、$2$ 回目に取り出されたカードはカード $2$ のとき、$x=5$, $y=7$ であり、$\max(x,y)=7$ となります。
• $1$ 回目に取り出されたカードがカード $2$ 、$2$ 回目に取り出されたカードはカード $1$ のとき、$x=7$, $y=5$ であり、$\max(x,y)=7$ となります。
• $1$ 回目に取り出されたカードがカード $2$ 、$2$ 回目に取り出されたカードもカード $2$ のとき、$x=y=7$ であり、$\max(x,y)=7$ となります。

これらが等確率で起こるため、期待値は $\frac{5+7+7+7}{4}=\frac{13}{2}$ となります。 $499122183\times 2\equiv 13 \pmod{998244353}$ であるため、$499122183$ を出力します。

7
22 75 26 45 72 81 47

22
249561150
110916092
873463862
279508479
360477194
529680742