Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Divide and Sum

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

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

Input

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

Output

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

Input

5 13 8 35 94 9284 34 54 69 123 846

Output

2588544

Note

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

- $$$p = [1]$$$, $$$q = [4]$$$, then $$$x = [1]$$$, $$$y = [4]$$$, $$$f(p, q) = |1 - 4| = 3$$$;
- $$$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$$$:

- $$$p = [2, 1]$$$, $$$q = [2, 1]$$$ (elements with indices $$$1$$$ and $$$2$$$ in the original array are selected in the subsequence $$$p$$$);
- $$$p = [2, 2]$$$, $$$q = [1, 1]$$$;
- $$$p = [2, 1]$$$, $$$q = [1, 2]$$$ (elements with indices $$$1$$$ and $$$4$$$ are selected in the subsequence $$$p$$$);
- $$$p = [1, 2]$$$, $$$q = [2, 1]$$$;
- $$$p = [1, 1]$$$, $$$q = [2, 2]$$$;
- $$$p = [2, 1]$$$, $$$q = [2, 1]$$$ (elements with indices $$$3$$$ and $$$4$$$ are selected in the subsequence $$$p$$$).

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/12/2021 08:39:56 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|