Вам задан массив \(a\) длины \(2n\). Рассмотрим разбиение массива \(a\) на две подпоследовательности \(p\) и \(q\) длины \(n\) (каждый элемент массива \(a\) должен попасть ровно в одну подпоследовательность: в \(p\) или в \(q\)).
Отсортируем \(p\) по неубыванию, а \(q\) — по невозрастанию, и получим последовательности \(x\) и \(y\), соответственно. Тогда назовём стоимостью разбиения \(f(p, q) = \sum_{i = 1}^n |x_i - y_i|\).
Вам необходимо найти сумму \(f(p, q)\) по всем корректным разбиениям массива \(a\). Так как это число может быть слишком большим, требуется посчитать остаток от деления его на \(998244353\).
В первой строке задано единственное целое число \(n\) (\(1 \leq n \leq 150\,000\)).
Во второй строке заданы \(2n\) целых чисел \(a_1, a_2, \ldots, a_{2n}\) (\(1 \leq a_i \leq 10^9\)) — элементы массива \(a\).
Выведите одно целое число — ответ на задачу по модулю \(998244353\).
Два разбиения массива считаются различными, если отличаются наборы индексов элементов, входящих в подпоследовательность \(p\).
В первом примере существует два корректных разбиения массива \(a\):
Во втором примере существует шесть корректных разбиений массива \(a\):
1 1 4
6
2 2 1 2 1
12
3 2 2 2 2 2 2
0
5 13 8 35 94 9284 34 54 69 123 846
2588544
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач