Допоможіть Прапору#11125
Прапору не до жартів, він вирішив взяти участь у контесті. Допоможіть йому розв'язати задачу. Розглянемо масив з чисел, де є непарним числом. Побудуємо повний зважений граф, що містить n + 1 вершину. Вага ребра між вершинами і (1 \le u < v \le n) визначається як максимум з a_u, a_{u+1}, \ldots, a_{v-1}. Вартістю масиву називається максимальна вага ідеального паросполучення в побудованому графі. Ідеальним паросполученням є таке паросполучення, яке покриває всі вершини.
Вам надано масив , що складається з різних цілих чисел. Обчисліть суму вартостей усіх перестановок масиву за модулем .
У першому рядку подано одне ціле непарне число - довжина масиву (1 \le n \le 10^5). У другому рядку наведено різних цілих чисел a_1, a_2, \ldots, a_n (1 \le a_i \le 10^8).
Виведіть одне число - суму вартостей усіх перестановок масиву за модулем .
Приклад 1