28661번 - Помогите Прапору 다국어

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

Рассмотрим массив $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$.