题目描述

有 $N$ 张卡片，编号从 $1$ 到 $N$。第 $i$ 张卡片上写有整数 $A_i$。这里，$N$ 是偶数。

Snuke 和 Robot 将进行以下游戏。

• 游戏主持人给 Snuke 和 Robot 公布一个 $(p_1,p_2,\\cdots,p_N)$ 的排列，其中 $(p_1,p_2,\\cdots,p_N)$ 是 $(1,2,\\cdots,N)$ 的一个排列。
• 接下来，Snuke 和 Robot 交替进行回合，Snuke 先开始。每个回合如下进行：
  • Snuke 的回合：选择一张剩余的卡片并吃掉它。
  • Robot 的回合：选择 $p_i$ 最大的卡片 $i$ 并将其烧掉。
• 当没有卡片剩余时，游戏结束。

游戏的最终得分是 Snuke 吃掉的卡片上的整数之和。为了获得最高得分，Snuke 将采取最优策略进行游戏。

$(1,2,\\cdots,N)$ 有 $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)$ 时，游戏进行如下：

• Snuke 吃掉卡片 $3$。
• Robot 烧掉卡片 $1$。
• Snuke 吃掉卡片 $4$。
• Robot 烧掉卡片 $2$。

这里游戏的得分是 $1010000$。

示例输入 3

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

示例输出 3

710984634