Помогите Прапору
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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