{"problem":{"name":"Double Chance","description":{"content":"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 th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc276_f"},"statements":[{"statement_type":"Markdown","content":"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.\nFor $K=1, 2, \\ldots, N$, solve the following problem.\n\n> We have a bag that contains $K$ cards: card $1$, card $2$, $\\ldots$, card $K$.  \n> Let us perform the following operation twice, and let $x$ and $y$ be the numbers recorded, in the recorded order.\n> \n> > Draw a card from the bag uniformly at random, and record the number written on that card. Then, **return the card to the bag**.\n> \n> Print the expected value of $\\max(x,y)$, modulo $998244353$ (see Notes).  \n> Here, $\\max(x,y)$ denotes the value of the greater of $x$ and $y$ (or $x$ if they are equal).\n\n## Constraints\n\n*   $1 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq A_i \\leq 2\\times 10^5$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n\n[samples]\n\n## Notes\n\nIt 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$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc276_f","tags":[],"sample_group":[["3\n5 7 5","5\n499122183\n443664163\n\nFor instance, the answer for $K=2$ is found as follows.\nThe bag contains card $1$ and card $2$, with $A_1=5$ and $A_2=7$ written on them, respectively.\n\n*   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$.\n*   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$.\n*   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$.\n*   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$.\n\nThese 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."],["7\n22 75 26 45 72 81 47","22\n249561150\n110916092\n873463862\n279508479\n360477194\n529680742"]],"created_at":"2026-03-03 11:01:13"}}