{"problem":{"name":"Affine Sort","description":{"content":"Given is a sequence of $N$ positive integers $X = (X_1, X_2, \\ldots, X_N)$. For a positive integer $K$, let $f(K)$ be the number of triples of integers $(a,b,c)$ that satisfy all of the following cond","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc126_f"},"statements":[{"statement_type":"Markdown","content":"Given is a sequence of $N$ positive integers $X = (X_1, X_2, \\ldots, X_N)$.\nFor a positive integer $K$, let $f(K)$ be the number of triples of integers $(a,b,c)$ that satisfy all of the following conditions.\n\n*   $1\\leq c \\leq K$.\n*   $0\\leq a < c$ and $0\\leq b < c$.\n*   For each $i$, let $Y_i$ be the remainder when $aX_i + b$ is divided by $c$. Then, $Y_1 < Y_2 < \\cdots < Y_N$ holds.\n\nIt can be proved that the limit $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3}$ exists. Find this value modulo $998244353$ (see Notes).\n\n## Constraints\n\n*   $2\\leq N\\leq 10^3$\n*   $X_i$ are positive integers such that $\\sum_{i=1}^N X_i \\leq 5\\times 10^5$.\n*   $X_i\\neq X_j$ if $i\\neq j$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$X_1$ $X_2$ $\\ldots$ $X_N$\n\n[samples]\n\n## Notes\n\nWe can prove that the limit in question is always a rational number. Additionally, under the Constraints of this problem, when that number is represented as $\\frac{P}{Q}$ using two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R\\times Q\\equiv P\\pmod{998244353}$ and $0\\leq R < 998244353$. Find this $R$.","is_translate":false,"language":"English"}],"meta":{"iden":"arc126_f","tags":[],"sample_group":[["3\n3 1 2","291154603\n\n*   For example, when $(a,b,c) = (3,5,7)$, we have $Y_1 = 0$, $Y_2 = 1$, $Y_3 = 4$, which satisfy $Y_1 < Y_2 < Y_3$.\n*   We have $f(1) = 0$, $f(2) = 0$, $f(3) = 1$, $f(4) = 2$, $f(5) = 5$.\n*   We have $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3} = \\frac{1}{24}$."],["3\n5 9 2","832860616\n\nWe have $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3} = \\frac{55}{1008}$ ."],["2\n2 3","166374059\n\nWe have $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3} = \\frac{1}{6}$."],["4\n4 5 3 2","0\n\nWe have $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3} = 0$."]],"created_at":"2026-03-03 11:01:14"}}