Помогите Прапору

Прапору не до шуток, он решил поучаствовать в контесте. Просто помогите ему решить задачу.

Рассмотрим массив $a$ из $n$ чисел, где $n$ --- нечетно. Построим полный взвешенный граф, в котором будет $n + 1$ вершина. Вес ребра между вершинами $u$ и $v$ ($1 \le u < v \le n$) равен максимуму из $a\_u$, $a\_{u + 1}$, \dots, $a\_{v - 1}$. Стоимостью массива $a$ назовем максимальный вес идеального паросочетания в построенном графе. Идельным паросочетанием называется паросочетание, покрывающее все вершины.

Вам дан массив $a$, состоящий из $n$ различных целых чисел. Вычислите сумму стоимостей всех перестановок массива $a$ по модулю $998\\,244\\,353$.

В первой строке дано одно целое нечетное число $n$ --- длина массива $a$ ($1 \le n \le 100\\,000$).

Во второй строке даны $n$ различных целых чисел $a\_1$, $a\_2$, \dots $a\_n$ ($1 \le a\_i \le 10^8$).

Выведите одно число --- сумму стоимостей всех перестановок массива $a$ по модулю $998\\,244\\,353$.