Задача №114712. Разбивай и суммируй
Вам дан массив \(a\) длины \(2n\). Рассмотрим разбиение массива \(a\) на две подпоследовательности \(p\) и \(q\) длины \(n\). Отсортируем \(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\):
- \(p = [1]\), \(q = [4]\), тогда \(x = [1]\), \(y = [4]\), \(f(p, q) = |1 - 4| = 3\)
- \(p = [4]\), \(q = [1]\), тогда \(x = [4]\), \(y = [1]\), \(f(p, q) = |4 - 1| = 3\).
Во втором примере существует шесть корректных разбиений массива \(a\):
- \(p = [2, 1]\), \(q = [2, 1]\) (в подпоследовательность \(p\) выбраны элементы с индексами \(1\) и \(2\) в исходном массиве).
- \(p = [2, 2]\), \(q = [1, 1]\).
- \(p = [2, 1]\), \(q = [2, 1]\) (в подпоследовательность \(p\) выбраны элементы с индексами \(1\) и \(4\) в исходном массиве).
- \(p = [1, 2]\), \(q = [2, 1]\).
- \(p = [1, 1]\), \(q = [2, 2]\).
- \(p = [2, 1]\), \(q = [2, 1]\) (в подпоследовательность \(p\) выбраны элементы с индексами \(3\) и \(4\) в исходном массиве).
1 1 4
6
2 2 1 2 1
12
3 2 2 2 2 2 2
0