题目描述

有 $N$ 张编号为 $1$ 到 $N$ 的卡牌，每张卡牌 $i$ 上写有一个整数 $A_i$。其中 $N$ 是偶数。

すぬけくん和机器人进行一场游戏。游戏流程如下：

• 游戏主持人会宣布一个 $1$ 到 $N$ 的排列 $p = (p_1, p_2, \cdots, p_N)$。这个排列すぬけくん和机器人都知道。
• 接下来，从すぬけくん开始，双方轮流进行操作。每一回合的操作如下：
  • すぬけくん的回合：从剩下的卡牌中任选一张，吃掉它。
  • 机器人的回合：从剩下的卡牌中，选择 $p_i$ 最大的那张卡牌 $i$，烧掉它。
• 当所有卡牌都被取走后，游戏结束。

最终游戏的得分为すぬけくん吃掉的卡牌上整数的总和。すぬけくん会采取最优策略，使得得分最大。

排列 $p$ 有 $N!$ 种可能。请你对于所有可能的排列 $p$，求出游戏得分的总和，并对 $998244353$ 取模后输出。

输入格式

输入为一行，格式如下：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出一个整数，表示答案。

样例 1

输入

2
1 2

输出

4

样例 2

输入

4
1 100 10000 1000000

输出

24200400

样例 3

输入

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

输出

710984634

说明/提示

限制条件

• $1 \leq N \leq 10^6$
• $N$ 是偶数
• $1 \leq A_i \leq 10^9$
• 输入的所有值均为整数

样例解释 1

无论排列 $p$ 如何，すぬけくん都会吃掉卡牌 $2$。

样例解释 2

例如，当 $p=(3,1,4,2)$ 时，游戏流程如下：

• すぬけくん吃掉卡牌 $3$。
• 机器人烧掉卡牌 $1$。
• すぬけくん吃掉卡牌 $4$。
• 机器人烧掉卡牌 $2$。 此时，游戏得分为 $1010000$。

由 ChatGPT 4.1 翻译