33OJ
登录 注册

#P17777. 甘织玲奈子不是罪过

甘织玲奈子不是罪过

背景

『再次孤单一人绝对不要!我要过上最棒的学校生活!』

『恋人只能有一个,但朋友却能交很多个!』

『一决胜负吧,看看符合我们的关系到底是恋人还是挚友!』

题目描述

玲奈子有 nn 个挚友,她们都想当玲奈子唯一的好朋友,所以玲奈子需要开导她们,其中第 ii 个挚友的好感度为 aia_i,初始时每个挚友都尚未被尝试开导过,当然也没有被开导成功。

定义被尝试开导过但尚未开导成功的挚友集合为 SS,尚未被尝试开导过的挚友集合为 TT,玲奈子的开导优先级序列为:

$$b_i=\begin{cases} a_i &i\in S\\ \frac{1}{2} &i=\min_{x\in T}x\\ 0 &\text{otherwise} \end{cases}$$

则玲奈子本次尝试开导 xx 的概率为 bx∑i=1nbi\frac{b_x}{\sum_{i=1}^nb_i}。若尝试开导 xx,有 axa_x 的概率开导成功。

玲奈子好奇她开导成功所有挚友的期望尝试次数,于是她把这个问题交给了你。给定 aa 在模 998244353998244353 意义下的值,请输出答案模 998244353998244353 的结果。

输入格式

第一行输入 nn。

接下来一行输入 nn 个正整数,第 ii 个数表示 aia_i。

输出格式

输出一行一个整数表示答案。

7
4 1 3 1 1 2 5
183011469

提示

对所有数据,满足 1≤n≤1061\le n\le 10^6,1≤ai<9982443531\le a_i<998244353。


要挚友不要恋人什么的,我只是害怕被伤害而已。