102765: [AtCoder]ABC276 F - Double Chance

Problem Statement

There are $N$ cards called card $1$, card $2$, $\ldots$, card $N$. On card $i$ $(1\leq i\leq N)$, an integer $A_i$ is written.

For $K=1, 2, \ldots, N$, solve the following problem.

We have a bag that contains $K$ cards: card $1$, card $2$, $\ldots$, card $K$.
Let us perform the following operation twice, and let $x$ and $y$ be the numbers recorded, in the recorded order.

Draw a card from the bag uniformly at random, and record the number written on that card. Then, return the card to the bag.

Print the expected value of $\max(x,y)$, modulo $998244353$ (see Notes).
Here, $\max(x,y)$ denotes the value of the greater of $x$ and $y$ (or $x$ if they are equal).

Notes

It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as $\frac{P}{Q}$ with two coprime integers $P$ and $Q$, it can be proved that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Print this $R$.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 2\times 10^5$
• All values in the input are integers.

Input

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

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

Output

Print $N$ lines. The $i$-th line $(1\leq i\leq N)$ should contain the answer to the problem for $K=i$.

Sample Input 1

3
5 7 5

Sample Output 1

5
499122183
443664163

For instance, the answer for $K=2$ is found as follows.

The bag contains card $1$ and card $2$, with $A_1=5$ and $A_2=7$ written on them, respectively.

• If you draw card $1$ in the first draw and card $1$ again in the second draw, we have $x=y=5$, so $\max(x,y)=5$.
• If you draw card $1$ in the first draw and card $2$ in the second draw, we have $x=5$ and $y=7$, so $\max(x,y)=7$.
• If you draw card $2$ in the first draw and card $1$ in the second draw, we have $x=7$ and $y=5$, so $\max(x,y)=7$.
• If you draw card $2$ in the first draw and card $2$ again in the second draw, we have $x=y=7$, so $\max(x,y)=7$.

These events happen with the same probability, so the sought expected value is $\frac{5+7+7+7}{4}=\frac{13}{2}$. We have $499122183\times 2\equiv 13 \pmod{998244353}$, so $499122183$ should be printed.

Sample Input 2

7
22 75 26 45 72 81 47

Sample Output 2

22
249561150
110916092
873463862
279508479
360477194
529680742

问题描述

有N张卡片，分别叫做卡片1，卡片2，$\ldots$，卡片N。在卡片i $(1\leq i\leq N)$上写有一个整数$A_i$。

对于$K=1, 2, \ldots, N$，解决以下问题。

我们有一个袋子，里面装有$K$张卡片：卡片1，卡片2，$\ldots$，卡片$K$。
让我们执行以下操作两次，并将记录下来的数记为$x$和$y$。

从袋子里随机抽出一张卡片，并记录下写在卡片上的数。然后，将卡片**放回袋子**。

输出$\max(x,y)$的期望值，对$998244353$取模（见注意事项）。
这里，$\max(x,y)$表示$x$和$y$中较大的那个数（或如果它们相等，则为$x$）。

注意事项

可以证明所求期望值总是有限且有理的。此外，在本问题的约束下，当该值表示为$\frac{P}{Q}$时，其中$P$和$Q$是互质的整数，可以证明存在一个整数$R$，使得$R \times Q \equiv P\pmod{998244353}$且$0 \leq R \lt 998244353$。输出这个$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$问题的答案。

样例输入1

3
5 7 5

样例输出1

5
499122183
443664163

例如，对于$K=2$的答案如下所示。

袋子里装有卡片1和卡片2，分别写有$A_1=5$和$A_2=7$。

• 如果你第一次抽到卡片1，第二次又抽到卡片1，那么$x=y=5$，所以$\max(x,y)=5$。
• 如果你第一次抽到卡片1，第二次抽到卡片2，那么$x=5$，$y=7$，所以$\max(x,y)=7$。
• 如果你第一次抽到卡片2，第二次抽到卡片1，那么$x=7$，$y=5$，所以$\max(x,y)=7$。
• 如果你第一次抽到卡片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$。

样例输入2

7
22 75 26 45 72 81 47

样例输出2

22
249561150
110916092
873463862
279508479
360477194
529680742