该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

这是问题的困难版本。在这个版本中 $n\leq2*10^5$。

阿兔最近沉迷于研究序列的中位数。他发现，对于一个序列的所有子序列，它们的中位数之和可能隐藏着有趣的数学性质。现在，他给你一个序列，希望你帮他计算所有非空子序列的中位数之和。由于结果可能很大，你只需要输出它对 $998244353$ 取模后的值。

中位数的定义如下：

• 设一个排序后的序列 $B$ 的长度为 $m$，则中位数为 $B_ {(m + 1) / 2}$ (向下取整)
• 如 $[1, 2, 3, 4, 5]$ 的中位数是 $3$，$[1, 2, 3, 4]$ 的中位数是 $2$。
• 同时我们定义空序列 $[]$ 的中位数是 $0$。

由于答案可能很大，请输出答案取模 $998244353$ 后的结果。

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 2 \times 10^5)$，表示序列的长度。

第二行 $n$ 个整数 $A_1, A_2, \dots, A_n$ $(1 \leq A_i \leq 10^9)$，表示给定的序列。

输出格式

输出一个整数，表示所有非空子序列的中位数之和，对 $998244353$ 取模后的结果。

6
1 1 4 5 1 4

130

3
1 2 3

12