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$$$.
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$$$).
Print one integer: the sum of costs of all permutations of the given array, modulo $$$998\,244\,353$$$.
3 1 30 15
300