B. Divide and Sum
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

Examples
Input
1
1 4
Output
6
Input
2
2 1 2 1
Output
12
Input
3
2 2 2 2 2 2
Output
0
Input
5
13 8 35 94 9284 34 54 69 123 846
Output
2588544
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$$$).