两次机会

题目描述

有 $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$)。

输入格式

输入按以下格式从标准输入给出:

$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$,则有 $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

数据范围

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 2\times 10^5$
• 输入中的所有值均为整数。

提示

可以证明所求期望值总是有限的且为有理数。另外,在该问题的约束下,当该值表示为不可约分数 $\frac{P}{Q}$ 时,可以证明存在唯一的整数 $R$,使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。输出这个 $R$。