Contest Duration: - (local time) (120 minutes) Back to Home
F - Affine Sort /

Time Limit: 5 sec / Memory Limit: 1024 MB

### 問題文

N 項からなる正整数列 X = (X_1, X_2, \ldots, X_N) が与えられます。

• 1\leq c \leq K
• 0\leq a < c かつ 0\leq b < c
• i に対して aX_i + bc で割った余りを Y_i とするとき、Y_1 < Y_2 < \cdots < Y_N が成り立つ。

### 制約

• 2\leq N\leq 10^3
• X_i は正の整数で、\sum_{i=1}^N X_i \leq 5\times 10^5 を満たす
• i\neq j ならば X_i\neq X_j

### 入力

N
X_1 X_2 \ldots X_N

### 出力

\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3}\mod 998244353 で出力してください。

3
3 1 2

### 出力例 1

291154603
• 例えば (a,b,c) = (3,5,7) とすると、Y_1 = 0, Y_2 = 1, Y_3 = 4 となり、Y_1 < Y_2 < Y_3 が成り立ちます。
• f(1) = 0, f(2) = 0, f(3) = 1, f(4) = 2, f(5) = 5 が成り立ちます。
• \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{24} が成り立ちます。

3
5 9 2

### 出力例 2

832860616

\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{55}{1008} が成り立ちます。

2
2 3

### 出力例 3

166374059

\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{6} が成り立ちます。

4
4 5 3 2

### 出力例 4

0

\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = 0 が成り立ちます。

Score : 1100 points

### Problem Statement

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 conditions.

• 1\leq c \leq K.
• 0\leq a < c and 0\leq b < c.
• 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.

It can be proved that the limit \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} exists. Find this value modulo 998244353 (see Notes).

### Notes

We 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.

### Constraints

• 2\leq N\leq 10^3
• X_i are positive integers such that \sum_{i=1}^N X_i \leq 5\times 10^5.
• X_i\neq X_j if i\neq j.

### Input

Input is given from Standard Input in the following format:

N
X_1 X_2 \ldots X_N

### Output

Print \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} modulo 998244353.

3
3 1 2

### Sample Output 1

291154603
• 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.
• We have f(1) = 0, f(2) = 0, f(3) = 1, f(4) = 2, f(5) = 5.
• We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{24}.

3
5 9 2

### Sample Output 2

832860616

We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{55}{1008} .

2
2 3

### Sample Output 3

166374059

We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = \frac{1}{6}.

4
4 5 3 2

### Sample Output 4

0

We have \displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3} = 0.