现在，你正在玩一个简单的游戏。给定一个长度为 $n$ 的数组 $A$，你的任务是控制一个机器人在该数组中移动或停止。

初始时，机器人的位置是随机选择的：选择位置 $i \in [1, n]$ 的概率为 $\frac{1}{n}$。在每一轮中，你知道当前的位置，并需要在两个动作选项之间做出决定：

• 停止 (Stop)。如果选择此动作，游戏立即结束。当机器人在位置 $i$ 停止时，你的得分为 $A_i$。
• 移动 (Move)。如果选择此动作且机器人位于位置 $i$，机器人将有 50% 的概率移动到 $i - 1$，有 50% 的概率移动到 $i + 1$。注意，当机器人位于位置 $1$ 或 $n$ 时，你不能选择此动作。

由于第二个动作只能在机器人不在数组两端时选择，我们可以证明，对于任何策略，都有 $\lim_{m \to +\infty} f(m) = 0$，其中 $f(m)$ 表示游戏在 $m$ 轮后仍在继续的概率。

你的任务是最大化游戏的期望得分。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)。 第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$ ($1 \le A_i \le 10^{12}$)。

输出格式

输出一行，包含一个整数：最大可能的期望得分，以分数模 $998\,244\,353$ 的形式表示。 换句话说，可以证明答案可以表示为一个有理数 $P/Q$，其中 $Q$ 与 $998\,244\,353$ 互质，你需要输出 $(P \cdot Q^{-1}) \pmod{998\,244\,353}$。

样例

输入 1

3
3 1 2

输出 1

499122179

输入 2

6
6 1 2 5 3 4

输出 2

582309211