AT_arc128_f [ARC128F] Game against Robot

有 $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 \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 翻译