分数: 1000 点
问题陈述
有 N 卡片编号 1 to N。卡 i 有一个整数 上面写着 A_i 。 在这里, N 是偶数。
Snuke 和 Robot 将玩一场游戏,游戏流程如下。
- 游戏主公布排列 (p_1,p_2,\cdots,p_N) of (1,2,\cdots,N),适用于 Snuke 和 Robot。
- 然后,Snuke和Robot轮流轮流,Snuke先走。
每回合如下。
- Snuke的回合:选择他选择的剩余一张牌并将其吃掉。
- 机器人回合:选择卡牌 i 拥有最大的 p_i 并烧掉它。
- 当没有更多牌时游戏结束。
游戏的最终得分是Snuke吃掉的卡片上写的整数之和。 Snuke 会以最佳方式发挥以最大化分数。
有 N! 排列 p of (1,2,\cdots,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, Snuke 会吃卡牌 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