Прапору не до шуток, он решил поучаствовать в контесте. Просто помогите ему решить задачу. Рассмотрим массив a из n чисел, где n нечетно. Построим полный взвешенный граф, в котором будет n + 1 вершина. Вес ребра между вершинами u и v (1 ≤ u < v ≤ n) равен максимуму из au, au+1, ..., av-1. Стоимостью массива a назовем максимальный вес идеального паросочетания в построенном графе. Идельным паросочетанием называется паросочетание, покрывающее все вершины.

Вам дан массив a, состоящий из n различных целых чисел. Вычислите сумму стоимостей всех перестановок массива a по модулю 998 244 353.

Входные данные

В первой строке дано одно целое нечетное число n - длина массива a (1 ≤ n ≤ 105). Во второй строке даны n различных целых чисел a1, a2, ..., an (1 ≤ ai ≤ 108).

Выходные данные

Выведите одно число - сумму стоимостей всех перестановок массива a по модулю 998 244 353.