题目描述

你正在调试一台在数轴数组上移动的机器人。数组 $A$ 的长度为 $n$，第 $i$ 个位置的奖励为 $A_i$。

游戏开始时，机器人的初始位置等概率随机选取：对于每个 $i\in[1,n]$，机器人位于位置 $i$ 的概率都是

每一回合，你都知道机器人当前所在位置，并需要在以下两种操作中选择一种：

• 停止：游戏立即结束。如果机器人停在位置 $i$，你的得分为 $A_i$。
• 移动：如果机器人当前在位置 $i$，则它以 $\frac12$ 的概率移动到 $i-1$，以 $\frac12$ 的概率移动到 $i+1$。当机器人位于位置 $1$ 或位置 $n$ 时，不能选择该操作。

可以证明，对于任意策略，若 $f(m)$ 表示游戏在 $m$ 回合后仍未结束的概率，则

你的目标是最大化游戏得分的期望值。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $A_1,A_2,\ldots,A_n$。

输出格式

输出一行一个整数，表示最大期望得分在模 $998244353$ 意义下的值。

换句话说，可以证明答案能表示为有理数 $\frac{P}{Q}$，其中 $Q$ 与 $998244353$ 互质。你需要输出

数据范围

• $1\le n\le 5\cdot 10^5$；
• $1\le A_i\le 10^{12}$。

样例 1

输入

3
3 1 2

输出

499122179

样例 2

输入

6
6 1 2 5 3 4

输出

582309211