Divide and Sum
Contest: Codeforces Round 680 (Div. 1, based on Moscow Team Olympiad)
Difficulty rating: 1900
Tags: combinatorics, math, sortings

You are given an array $$$a$$$ of length $$$2n$$$. Consider a partition of array $$$a$$$ into two subsequences $$$p$$$ and $$$q$$$ of length $$$n$$$ each (each element of array $$$a$$$ should be in exactly one subsequence: either in $$$p$$$ or in $$$q$$$).

Let's sort $$$p$$$ in non-decreasing order, and $$$q$$$ in non-increasing order, we can denote the sorted versions by $$$x$$$ and $$$y$$$, respectively. Then the cost of a partition is defined as $$$f(p, q) = \sum_{i = 1}^n |x_i - y_i|$$$.

Find the sum of $$$f(p, q)$$$ over all correct partitions of array $$$a$$$. Since the answer might be too big, print its remainder modulo $$$998244353$$$.

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

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

Output format:
Print one integer — the answer to the problem, modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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

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 array $$$a$$$:

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

Example input:
1
1 4

Example output:
6

Example input:
2
2 1 2 1

Example output:
12

Editorial:
No matter how we split the array, the cost of a partition will always be the same.
Let's prove it. Without loss of generality we will consider that the array $$$a$$$ sorted and denote for $$$L$$$ the set of elements with indexes from $$$1$$$ to $$$n$$$, and for $$$R$$$ the set of elements with indexes from $$$n + 1$$$ to $$$2n$$$.
Then split the array $$$a$$$ into any two arrays $$$p$$$ and $$$q$$$ of size $$$n$$$. Let's sort $$$p$$$ in non-decreasing order and $$$q$$$ by non-increasing order. Any difference $$$|p_i - q_i|$$$ in our sum will be the difference of one element of $$$R$$$ and one element of $$$L$$$.
If this is not the case, then there is an index $$$i$$$ such that both $$$p_i$$$ and $$$q_i$$$ belong to the same set. Let's assume that this is $$$L$$$.
1. All elements with indexes less than or equal to $$$i$$$ in $$$p$$$ belong to $$$L$$$ ($$$i$$$ elements)
2. All items with indexes greater than or equal to $$$i$$$ in $$$q$$$ belong to $$$L$$$ ($$$n - (i - 1)$$$ elements)
Then $$$L$$$ has at least $$$i + n - (i-1) = n + 1$$$ elements, but there must be exactly $$$n$$$. Contradiction. For the set $$$R$$$ the proof is similar.
Then the answer to the problem is (the sum of the elements of the set $$$R$$$ minus the sum of the elements of the set $$$L$$$) multiplied by the number of partitions of the array $$$C^{n}_{2n}$$$.
Complexity: $$$O(n \log n)$$$ (due to sorting)