J. Split and sum
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

Print one integer number  — 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
Note

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