Допоможіть Прапору
Прапору не до жартів, він вирішив взяти участь у контесті. Допоможіть йому розв'язати задачу. Розглянемо масив a з n чисел, де n є непарним числом. Побудуємо повний зважений граф, що містить n + 1 вершину. Вага ребра між вершинами u і v (1 ≤ u < v ≤ n) визначається як максимум з a[u], a[u+1], ..., a[v-1]. Вартістю масиву a називається максимальна вага ідеального паросполучення в побудованому графі. Ідеальним паросполученням є таке паросполучення, яке покриває всі вершини.
Вам надано масив a, що складається з n різних цілих чисел. Обчисліть суму вартостей усіх перестановок масиву a за модулем 998 244 353.
Вхідні дані
У першому рядку подано одне ціле непарне число n - довжина масиву a (1 ≤ n ≤ 10^5). У другому рядку наведено n різних цілих чисел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^8).
Вихідні дані
Виведіть одне число - суму вартостей усіх перестановок масиву a за модулем 998 244 353.