题目描述

给定一个由 $N$ 项组成的正整数序列 $X = (X_1, X_2, \ldots, X_N)$。

对于正整数 $K$，记满足以下所有条件的整数三元组 $(a, b, c)$ 的个数为 $f(K)$：

• $1 \leq c \leq K$
• $0 \leq a < c$ 且 $0 \leq b < c$
• 对于每个 $i$，令 $Y_i$ 为 $aX_i + b$ 除以 $c$ 的余数，当且仅当 $Y_1 < Y_2 < \cdots < Y_N$ 时成立。

可以证明极限 $\displaystyle \lim_{K \to \infty} \frac{f(K)}{K^3}$ 存在。请计算该值对 $998244353$ 取模的结果（见注释）。

输入格式

输入通过标准输入按以下格式给出。

$N$ $X_1$ $X_2$ $\ldots$ $X_N$

输出格式

输出 $\displaystyle \lim_{K \to \infty} \frac{f(K)}{K^3}$ 对 $998244353$ 取模的结果。

样例 1

输入

3
3 1 2

输出

291154603

样例 2

输入

3
5 9 2

输出

832860616

样例 3

输入

2
2 3

输出

166374059

样例 4

输入

4
4 5 3 2

输出

0

说明/提示

注释

可以证明所求极限一定是有理数。在本题的约束下，若用互质的两个整数 $P, Q$ 表示该值为 $\frac{P}{Q}$，则一定存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

约束条件

• $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$

样例解释 1

• 例如当 $(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}$。

样例解释 2

$\displaystyle \lim\_{K \to \infty} \frac{f(K)}{K^3} = \frac{55}{1008}$。

样例解释 3

$\displaystyle \lim\_{K \to \infty} \frac{f(K)}{K^3} = \frac{1}{6}$。

样例解释 4

$\displaystyle \lim\_{K \to \infty} \frac{f(K)}{K^3} = 0$。

由 ChatGPT 4.1 翻译