Divide and Sum

2000ms

524288K

Description:

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:

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:

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

Sample Input:

1
1 4

Sample Output:

Sample Input:

2
2 1 2 1

Sample Output:

Sample Input:

3
2 2 2 2 2 2

Sample Output:

Sample Input:

5
13 8 35 94 9284 34 54 69 123 846

Sample Output:

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

$$$p = [1]$$$, $$$q = [4]$$$, then $$$x = [1]$$$, $$$y = [4]$$$, $$$f(p, q) = |1 - 4| = 3$$$;
$$$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$$$:

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

Informação

Provedor Codeforces

Código CF1444B