Codeforces Round #680 (Div. 2) Divide and Sum

Description

You are given an array aa of length 2n2n. Consider a partition of array aa into two subsequences pp and qq of length nn each (each element of array aa should be in exactly one subsequence: either in pp or in qq).

Let's sort pp in non-decreasing order, and qq in non-increasing order, we can denote the sorted versions by xx and yy, respectively. Then the cost of a partition is defined as

Find the sum of 

over all correct partitions of array aa. Since the answer might be too big, print its remainder modulo 998244353998244353.

題目大意：

給你2n個數，将它們分成p、q兩個序列，每個序列n個數，其中一個序列遞增，一個序列遞減（對它們分别排序），求所有劃分方案的

貢獻和。

Input

The first line contains a single integer nn (1≤n≤1500001≤n≤150000).

The second line contains 2n2n integers a1,a2,…,a2na1,a2,…,a2n (1≤ai≤1091≤ai≤109) — elements of array aa.

Output

Print one integer — the answer to the problem, modulo 998244353998244353.

Examples

input

Copy

1
1 4
      

output

Copy

6      

input

Copy

2
2 1 2 1
      

output

Copy

12      

input

Copy

3
2 2 2 2 2 2
      

output

Copy

input

Copy

5
13 8 35 94 9284 34 54 69 123 846
      

output

Copy

2588544      

Note

Two partitions of an array are considered different if the sets of indices of elements included in the subsequence pp are different.

In the first example, there are two correct partitions of the array aa:

1. p=[1]p=[1], q=[4]q=[4], then x=[1]x=[1], y=[4]y=[4], f(p,q)=|1−4|=3f(p,q)=|1−4|=3;
2. p=[4]p=[4], q=[1]q=[1], then x=[4]x=[4], y=[1]y=[1], f(p,q)=|4−1|=3f(p,q)=|4−1|=3.

In the second example, there are six valid partitions of the array aa:

1. p=[2,1]p=[2,1], q=[2,1]q=[2,1] (elements with indices 11 and 22 in the original array are selected in the subsequence pp);
2. p=[2,2]p=[2,2], q=[1,1]q=[1,1];
3. p=[2,1]p=[2,1], q=[1,2]q=[1,2] (elements with indices 11 and 44 are selected in the subsequence pp);
4. p=[1,2]p=[1,2], q=[2,1]q=[2,1];
5. p=[1,1]p=[1,1], q=[2,2]q=[2,2];
6. p=[2,1]p=[2,1], q=[2,1]q=[2,1] (elements with indices 33 and 44 are selected in the subsequence pp).

Solution

通過格物緻知，可以發現所有方案的貢獻是一樣的。

且将原序列排序後，前n個（設為集合A）的貢獻為-a[i]，後n個（設為集合B）的貢獻為a[i]（加了絕對值之後）。

考慮簡單證明：

假設p序列中選了i個集合A的數，則另外n-i個為集合B中的數。那麼在q序列中有n-i個集合A的數，以及i個集合B中的數。

此時假設将p從小到大排序，将q從大到小排序，

p中的i個集合A的數一定對應q中的i個集合B中的數，

且p中n-i個集合B的數一定對應q中n-i個集合A中的數。

由于集合A中的數一定小于等于集合B中的數，

那麼相減取絕對值之後A中貢獻一定為它的相反數，B中數一定是它本身。

證畢。

那麼隻需用排序後的後n個數減去前n個數乘以劃分集合的方案書即可。

Code

#include<cstdio>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(register ll i=a;i<=b;i++)
#define Fd(i,a,b) for(register ll i=a;i>=b;i--)
#define N 300005
#define M 998244353
using namespace std;
ll T,n,f[N],inv[N],a[N],ans;
void R(ll &x){
	x=0;I w=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	x*=w;
}
ll ksm(ll x,ll k){
	ll sum=1;
	for(;k;k>>=1,x=(x*x)%M) if(k&1) sum=(sum*x)%M;
	return sum;
}
ll C(ll n,ll m){
	return f[n]*inv[m]%M*inv[n-m]%M;
}
I main(){
//	freopen("Divide and Sum.in","r",stdin);
//	freopen("Divide and Sum.out","w",stdout);
	f[0]=1;
	F(i,1,300000) f[i]=(1ll*f[i-1]*i)%M;
	inv[300000]=ksm(f[300000],M-2);
	Fd(i,300000-1,0) inv[i]=(1ll*inv[i+1]*(i+1))%M;
	R(n);
	F(i,1,n*2) R(a[i]);
	sort(a+1,a+1+n*2);
	F(i,1,n){
		ans=(ans+a[n*2-i+1]-a[i])%M;
	}
	ans=ans*C(2*n,n)%M;
	printf("%lld\n",ans);
	return 0;
}