Help Prapor

Prapor is in no mood for jokes, but he has decided to take part in a contest. Just help him solve the problem.

Consider an array $a$ of $n$ numbers, where $n$ is odd. Build a complete weighted graph with $n + 1$ vertices. The weight of the edge between vertices $u$ and $v$ ($1 \le u < v \le n$) is the maximum of $a_u, a_{u+1}, \dots, a_{v-1}$. The cost of array $a$ is the maximum total weight of a perfect matching in this graph. A perfect matching is a matching that covers all vertices.

You are given an array $a$ of $n$ distinct integers. Compute the sum of the costs over all permutations of $a$, modulo $998\,244\,353$.

The first line contains one odd integer $n$, the length of array $a$ ($1 \le n \le 100\,000$). The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^8$).

Print one number: the sum of the costs of all permutations of $a$, modulo $998\,244\,353$.