Прапору не до шуток, он решил поучаствовать в контесте. Просто помогите ему решить задачу.
Рассмотрим массив $$$a$$$ из $$$n$$$ чисел, где $$$n$$$ — нечетно. Построим полный взвешенный граф, в котором будет $$$n + 1$$$ вершина. Вес ребра между вершинами $$$u$$$ и $$$v$$$ ($$$1 \le u < v \le n$$$) равен максимуму из $$$a_u$$$, $$$a_{u + 1}$$$, ..., $$$a_{v - 1}$$$. Стоимостью массива $$$a$$$ назовем максимальный вес идеального паросочетания в построенном графе. Идельным паросочетанием называется паросочетание, покрывающее все вершины.
Вам дан массив $$$a$$$, состоящий из $$$n$$$ различных целых чисел. Вычислите сумму стоимостей всех перестановок массива $$$a$$$ по модулю $$$998\,244\,353$$$.
В первой строке дано одно целое нечетное число $$$n$$$ — длина массива $$$a$$$ ($$$1 \le n \le 100\,000$$$).
Во второй строке даны $$$n$$$ различных целых чисел $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ ($$$1 \le a_i \le 10^8$$$).
Выведите одно число — сумму стоимостей всех перестановок массива $$$a$$$ по модулю $$$998\,244\,353$$$.
3 1 30 15
300