Прапору не до шуток, он решил поучаствовать в контесте. Просто помогите ему решить задачу. Рассмотрим массив 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.