/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
1 から N までの番号のついた N 枚のカードがあり，カード i には整数 A_i が書かれています． なお，N は偶数です．
すぬけくんとロボットがゲームをします． ゲームは，以下のように進行します．
- ゲームマスターが (1,2,\cdots,N) の順列 (p_1,p_2,\cdots,p_N) を宣言する． この順列はすぬけくんとロボット両方に知らされる．
- その後，すぬけくんからはじめて，両者が交互に手番をプレイする．
各手番では以下のことが起こる．
- すぬけくんの手番: 残っているカードの中から好きなものを一つ選び，食べる．
- ロボットの手番: 残っているカードのうち，p_i が最大となるカード i を選び，燃やす．
- カードがなくなったらゲームは終了する．
最終的なゲームのスコアは，すぬけくんが食べたカードに書かれた整数の総和です． すぬけくんは，ゲームのスコアを最大化するように最適な行動をします．
順列 p は N! 通り考えられますが，これらすべてについてゲームのスコアを求め，その総和を 998244353 で割った余りを求めてください．
制約
- 1 \leq N \leq 10^6
- N は偶数
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \cdots A_N
出力
答えを出力せよ．
入力例 1
2 1 2
出力例 1
4
順列 p に依らず，すぬけくんはカード 2 を食べます．
入力例 2
4 1 100 10000 1000000
出力例 2
24200400
例えば p=(3,1,4,2) であるとき，ゲームは以下のように進行します．
- すぬけくんがカード 3 を食べる．
- ロボットがカード 1 を燃やす．
- すぬけくんがカード 4 を食べる．
- ロボットがカード 2 を燃やす．
このとき，ゲームのスコアは 1010000 になります．
入力例 3
10 866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117
出力例 3
710984634
Score : 1000 points
Problem Statement
There are N cards numbered 1 to N. Card i has an integer A_i written on it. Here, N is even.
Snuke and Robot will play a game, which will go as follows.
- The game master announces a permutation (p_1,p_2,\cdots,p_N) of (1,2,\cdots,N), to both Snuke and Robot.
- Then, Snuke and Robot alternately take turns, with Snuke going first.
Each turn goes as follows.
- Snuke's turn: choose a remaining card of his choice and eat it.
- Robot's turn: choose Card i with the largest p_i and burn it.
- The game ends when there is no more card.
The final score of the game is the sum of integers written on the cards eaten by Snuke. Snuke will play optimally to maximize the score.
There are N! permutations p of (1,2,\cdots,N). Find the sum, modulo 998244353, of the final scores for all of these permutations.
Constraints
- 1 \leq N \leq 10^6
- N is even.
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
2 1 2
Sample Output 1
4
Regardless of the permutation p, Snuke will eat Card 2.
Sample Input 2
4 1 100 10000 1000000
Sample Output 2
24200400
For example, when p=(3,1,4,2), the game will go as follows.
- Snuke eats Card 3.
- Robot burns Card 1.
- Snuke eats Card 4.
- Robot burns Card 2.
The score of the game here is 1010000.
Sample Input 3
10 866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117
Sample Output 3
710984634