CF1444B Divide and Sum

给定一个长度为 $2n$ 的数组 $a$。请将数组 $a$ 分成两个长度为 $n$ 的子序列 $p$ 和 $q$（每个元素只能属于 $p$ 或 $q$ 中的一个）。 将 $p$ 按非降序排序，得到 $x$；将 $q$ 按非升序排序，得到 $y$。定义本次划分的代价为 $f(p, q) = \sum_{i = 1}^n |x_i - y_i|$。 请你求出所有合法划分的 $f(p, q)$ 之和。由于答案可能很大，请输出其对 $998244353$ 取模后的结果。

第一行包含一个整数 $n$（$1 \leq n \leq 150\,000$）。 第二行包含 $2n$ 个整数 $a_1, a_2, \ldots, a_{2n}$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。

输出一个整数，表示所有合法划分的 $f(p, q)$ 之和，对 $998244353$ 取模后的结果。

如果两个划分中，子序列 $p$ 所包含元素的下标集合不同，则认为这两个划分不同。 在第一个样例中，数组 $a$ 有两种合法划分： 1. $p = [1]$，$q = [4]$，则 $x = [1]$，$y = [4]$，$f(p, q) = |1 - 4| = 3$； 2. $p = [4]$，$q = [1]$，则 $x = [4]$，$y = [1]$，$f(p, q) = |4 - 1| = 3$。 在第二个样例中，数组 $a$ 有六种合法划分： 1. $p = [2, 1]$，$q = [2, 1]$（原数组中第 $1$ 和 $2$ 个元素选入 $p$）； 2. $p = [2, 2]$，$q = [1, 1]$； 3. $p = [2, 1]$，$q = [1, 2]$（原数组中第 $1$ 和 $4$ 个元素选入 $p$）； 4. $p = [1, 2]$，$q = [2, 1]$； 5. $p = [1, 1]$，$q = [2, 2]$； 6. $p = [2, 1]$，$q = [2, 1]$（原数组中第 $3$ 和 $4$ 个元素选入 $p$）。 由 ChatGPT 4.1 翻译