B. Разбивай и суммируй
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$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$$$.

Примеры
Входные данные
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
Примечание

Два разбиения массива считаются различными, если отличаются наборы индексов элементов, входящих в подпоследовательность $$$p$$$.

В первом примере существует два корректных разбиения массива $$$a$$$:

  1. $$$p = [1]$$$, $$$q = [4]$$$, тогда $$$x = [1]$$$, $$$y = [4]$$$, $$$f(p, q) = |1 - 4| = 3$$$
  2. $$$p = [4]$$$, $$$q = [1]$$$, тогда $$$x = [4]$$$, $$$y = [1]$$$, $$$f(p, q) = |4 - 1| = 3$$$.

Во втором примере существует шесть корректных разбиений массива $$$a$$$:

  1. $$$p = [2, 1]$$$, $$$q = [2, 1]$$$ (в подпоследовательность $$$p$$$ выбраны элементы с индексами $$$1$$$ и $$$2$$$ исходного массива);
  2. $$$p = [2, 2]$$$, $$$q = [1, 1]$$$;
  3. $$$p = [2, 1]$$$, $$$q = [1, 2]$$$ (в подпоследовательность $$$p$$$ выбраны элементы с индексами $$$1$$$ и $$$4$$$ исходного массива);
  4. $$$p = [1, 2]$$$, $$$q = [2, 1]$$$;
  5. $$$p = [1, 1]$$$, $$$q = [2, 2]$$$;
  6. $$$p = [2, 1]$$$, $$$q = [2, 1]$$$ (в подпоследовательность $$$p$$$ выбраны элементы с индексами $$$3$$$ и $$$4$$$).