Divide and Sum

题意翻译

给一个长度为 $2n$ 的数列 $a$，将 $a$ 中的数分为两串长度为 $n$ 的数列 $p$ 和 $q$ $PS:p,q$不一定要是数列 $a$ 中连续的数列。 例：$a=\{1,2,3,4\}$，那么可以为 $p=\{1,3\},q=\{4,2\}$，此时 $f(p,q)=|1-4|+|3-2|=3+1=4$。 我们按非递减的顺序对数列 $p$ 排序，而数列 $q$ 按非递增的顺序排序。然后我们定义 $f(p,q)=\sum_{i=1}^{n}|p_i-q_i|$。 求对于所有的 $p,q$ 的 $f(p,q)$ 的值之和。答案对 $998244353$ 取模。

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

1
1 4

输出样例 #1

6

输入样例 #2

2
2 1 2 1

输出样例 #2

12

输入样例 #3

3
2 2 2 2 2 2

输出样例 #3

0

输入样例 #4

5
13 8 35 94 9284 34 54 69 123 846

输出样例 #4

2588544

说明

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