当前没有测试数据。

F - 双倍机会

分值：500分

问题描述

现有$N$张卡片，编号从1到$N$，第$i$张卡片上写着整数$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$时的问题的答案。

3
5 7 5

5
499122183
443664163

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

袋子中有编号为1和2的卡片，分别写着5和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$。

7
22 75 26 45 72 81 47

22
249561150
110916092
873463862
279508479
360477194
529680742