← 返回题目列表

Codeforces · 1444/B

B. 除法与求和

中文机器翻译题面 查看原题

给你一个长度为$$$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$$$ 的元素)。