Funny Cost
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Cost of an array $$$a$$$ of (odd number) $$$n-1$$$ elements is the maximum weight of a perfect matching in the graph with $$$n$$$ vertices, where the weight of the edge between vertices $$$u$$$ and $$$v$$$ ($$$1 \leq u < v \leq n$$$) is the maximum value among $$$a_u, a_{u+1}, \ldots, a_{v-1}$$$.

You need to find the sum of costs of all permutations of the given array with $$$n$$$ different elements, modulo $$$998\,244\,353$$$.

Input

The first line contains one odd integer $$$n$$$ ($$$1 \leq n \leq 100\,000$$$).

The second line contains $$$n$$$ different elements $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^8$$$).

Output

Print one integer: the sum of costs of all permutations of the given array, modulo $$$998\,244\,353$$$.

Example

Input
3
1 30 15
Output
300