Problem Statement

A sequence obtained by concatenating a monotonically increasing sequence $X$ and a monotonically decreasing sequence $Y$, in this order, is called a mountain sequence.

Also, for a mountain sequence $\{x_1,x_2,...,x_n\}$ of length at least 2,
the maximum value among $|x_1 - x_2|,|x_2-x_3|,...,|x_{n-1}-x_n|$ is called the danger level of the sequence.
For example, the sequences $\{3, 7, 9, 4\}$ and $\{1, 2,4\}$ are both mountain sequences, and their danger levels are 5 and 2, respectively.

You are given a sequence of pairwise distinct positive integers $\{A_1,A_2,...,A_N\}$.
Find the danger level of every mountain sequence that can be obtained by rearranging it,
and output their sum $\bmod 998244353$.

Input

$N$
$A_1\ A_2\ ...\ A_N$

• $2 \le N \le 2500$
• $1 \le A_1 < A_2 < ... < A_N \le 2500$
• All inputs are integers

Output

Output the answer.
Print a newline at the end.

Sample

3
1 2 4

10

4
3 4 7 9

38