给你一个长度为$$$2n$$$的数组$$$a$$$。考虑将数组 $$$a$$$ 划分为两个子序列 $$$p$$$ 和 $$$q$$$,每个子序列的长度为 $$$n$$$(数组 $$$a$$$ 的每个元素应该恰好位于一个子序列中:要么在 $$$p$$$ 要么在 $$$q$$$ 中)。
让我们以非降序对 $$$p$$$ 进行排序,并以非升序对 $$$q$$$ 进行排序,我们可以分别用 $$$x$$$ 和 $$$y$$$ 来表示排序后的版本。那么分区的成本定义为 $$$f(p, q) = \sum_{i = 1}^n |x_i - y_i|$$$。
求 $$$f(p, q)$$$ 在数组 $$$a$$$ 的所有正确分区上的总和。由于答案可能太大,请打印其对 $$$998244353$$$ 取模后的余数。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 150\,000$$$)。
第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。
输出
打印一个整数——问题的答案,以 $$$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
注意
如果子序列 $$$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]$$$(在子序列$$$p$$$中选择原数组中索引为$$$1$$$和$$$2$$$的元素);
2. $$$p = [2, 2]$$$, $$$q = [1, 1]$$$;
3. $$$p = [2, 1]$$$, $$$q = [1, 2]$$$(在子序列$$$p$$$中选择索引为$$$1$$$和$$$4$$$的元素);
4. $$$p = [1, 2]$$$, $$$q = [2, 1]$$$;
5. $$$p = [1, 1]$$$, $$$q = [2, 2]$$$;
6. $$$p = [2, 1]$$$, $$$q = [2, 1]$$$(在子序列 $$$p$$$ 中选择索引为 $$$3$$$ 和 $$$4$$$ 的元素)。