410214: GYM103984 J Split and sum

An integer $$$ n $$$ and an array $$$ a $$$ of length $$$ 2n $$$ are given. Consider splitting the array $$$ a $$$ into two subsequences $$$ p $$$ and $$$ q $$$ of length $$$ n $$$. We sort $$$ p $$$ non-decreasing, and $$$ q $$$ non-increasing, and we get the sequences $$$ x $$$ and $$$ y $$$, respectively. Then we call the cost of the partition $$$ f(p, q) = \sum_{i = 1}^n |x_i - y_i|$$$.

Calculate the sum of $$$f(p, q)$$$ over all correct partitions of $$$ a $$$. Since this number can be truly huge, you need to calculate it modulo $$$998244353$$$. Ogneslav awaits his fiery deeds, so he asks to solve this problem for him.

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 150\,000$$$).

The second line contains $$$ 2n $$$ integer numbers $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_i \leq 10^9$$$)  — array elements.

Print one integer number  — the answer to the problem modulo $$$998244353$$$.

1
1 4

6

2
2 1 2 1

12

3
2 2 2 2 2 2

0

Two partitions of an array are considered different if the sets of indices of elements included in the subsequence $$$ p $$$ differ.

In the first example, there are two correct partitions of the array $$$ a $$$:

1. $$$ p = [1] $$$, $$$ q = [4] $$$, then $$$ x = [1] $$$, $$$ y = [4] $$$, $$$ f (p, q) = | 1 - 4 | = 3$$$
2. $$$ p = [4] $$$, $$$ q = [1] $$$, then $$$ x = [4] $$$, $$$ y = [1] $$$, $$$ f (p, q) = | 4 - 1 | = 3$$$.

In the second example, there are six valid partitions of the $$$ a $$$ array:

1. $$$ p = [2, 1] $$$, $$$ q = [2, 1] $$$, then $$$ x = [1, 2] $$$, $$$ y = [2, 1] $$$, $$$ f(p, q) = 2 $$$ (elements with indices 1 and 2 in the original array are selected in the subsequence $$$ p $$$).
2. $$$ p = [2, 2] $$$, $$$ q = [1, 1] $$$, then $$$ x = [2, 2] $$$, $$$ y = [1, 1] $$$, $$$ f(p, q) = $$$ 2.
3. $$$ p = [2, 1] $$$, $$$ q = [2, 1] $$$, then $$$ x = [1, 2] $$$, $$$ y = [2, 1] $$$, $$$ f(p, q) = 2 $$$ (elements with indices 1 and 4 are selected in the subsequence $$$ p $$$).
4. $$$ p = [1, 2] $$$, $$$ q = [2, 1] $$$, then $$$ x = [1, 2] $$$, $$$ y = [2, 1] $$$, $$$ f(p, q) = $$$ 2.
5. $$$ p = [1, 1] $$$, $$$ q = [2, 2] $$$, then $$$ x = [1, 1] $$$, $$$ y = [2, 2] $$$, $$$ f(p, q) = $$$ 2.
6. $$$ p = [2, 1] $$$, $$$ q = [2, 1] $$$, then $$$ x = [1, 2] $$$, $$$ y = [2, 1] $$$, $$$ f(p, q) = 2 $$$ (elements with indices 3 and 4 are selected in the subsequence $$$ p $$$).