CF1009E.Intercity Travelling

Leha is planning his journey from Moscow to Saratov. He hates trains, so he has decided to get from one city to another by car.

The path from Moscow to Saratov can be represented as a straight line (well, it's not that straight in reality, but in this problem we will consider it to be straight), and the distance between Moscow and Saratov is $n$ km. Let's say that Moscow is situated at the point with coordinate $0$ km, and Saratov — at coordinate $n$ km.

Driving for a long time may be really difficult. Formally, if Leha has already covered $i$ kilometers since he stopped to have a rest, he considers the difficulty of covering $(i + 1)$-th kilometer as $a_{i + 1}$. It is guaranteed that for every $i \in [1, n - 1]$ $a_i \le a_{i + 1}$. The difficulty of the journey is denoted as the sum of difficulties of each kilometer in the journey.

Fortunately, there may be some rest sites between Moscow and Saratov. Every integer point from $1$ to $n - 1$ may contain a rest site. When Leha enters a rest site, he may have a rest, and the next kilometer will have difficulty $a_1$, the kilometer after it — difficulty $a_2$, and so on.

For example, if $n = 5$ and there is a rest site in coordinate $2$, the difficulty of journey will be $2a_1 + 2a_2 + a_3$: the first kilometer will have difficulty $a_1$, the second one — $a_2$, then Leha will have a rest, and the third kilometer will have difficulty $a_1$, the fourth — $a_2$, and the last one — $a_3$. Another example: if $n = 7$ and there are rest sites in coordinates $1$ and $5$, the difficulty of Leha's journey is $3a_1 + 2a_2 + a_3 + a_4$.

Leha doesn't know which integer points contain rest sites. So he has to consider every possible situation. Obviously, there are $2^{n - 1}$ different distributions of rest sites (two distributions are different if there exists some point $x$ such that it contains a rest site in exactly one of these distributions). Leha considers all these distributions to be equiprobable. He wants to calculate $p$ — the expected value of difficulty of his journey.

Obviously, $p \cdot 2^{n - 1}$ is an integer number. You have to calculate it modulo $998244353$.

列哈计划从莫斯科开车前往萨拉托夫。他讨厌乘坐火车，因此决定自驾完成这段旅程。

从莫斯科到萨拉托夫的路径可视为一条直线（现实中并非完全笔直，但本题中我们将其视为直线），两地之间的距离为 $n$ 千米。设莫斯科位于坐标 $0$ 千米处，萨拉托夫位于坐标 $n$ 千米处。

长时间驾驶可能非常困难。形式化地，若列哈自上一次休息后已行驶了 $i$ 千米，则他将第 $(i + 1)$ 千米的困难度定义为 $a_{i + 1}$。题目保证对任意 $i \in [1, n - 1]$，均有 $a_i \le a_{i + 1}$。整个旅程的困难度定义为旅程中每一千米困难度之和。

幸运的是，莫斯科与萨拉托夫之间可能存在若干休息点。每个从 $1$ 到 $n - 1$ 的整数坐标点都可能设有休息点。当列哈进入一个休息点时，他可以选择休息；此后下一段 1 千米的困难度重置为 $a_1$，再下一段为 $a_2$，依此类推。

例如，若 $n = 5$，且在坐标 $2$ 处设有一个休息点，则旅程困难度为 $2a_1 + 2a_2 + a_3$：第一千米困难度为 $a_1$，第二千米为 $a_2$；随后列哈休息，第三千米困难度重置为 $a_1$，第四千米为 $a_2$，第五千米为 $a_3$。另一个例子：若 $n = 7$，且在坐标 $1$ 和 $5$ 处设有休息点，则列哈旅程的困难度为 $3a_1 + 2a_2 + a_3 + a_4$。

列哈并不知道哪些整数坐标点实际设置了休息点，因此他必须考虑所有可能的情形。显然，休息点分布的总数为 $2^{n - 1}$ 种（两种分布不同，当且仅当存在某个点 $x$，使得该点在其中一种分布中设有休息点而在另一种中没有）。列哈认为所有这些分布出现的概率均等。他希望计算 $p$ —— 旅程困难度的期望值。

显然，$p \cdot 2^{n - 1}$ 是一个整数。你需要计算该整数对 $998244353$ 取模的结果。

The first line contains one number $n$ ($1 \le n \le 10^6$) — the distance from Moscow to Saratov.

The second line contains $n$ integer numbers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_1 \le a_2 \le \dots \le a_n \le 10^6$), where $a_i$ is the difficulty of $i$-th kilometer after Leha has rested.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示从莫斯科到萨拉托夫的距离（单位：千米）。

第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$（$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^6$），其中 $a_i$ 表示 Leha 休息后第 $i$ 千米的难度。

Print one number — $p \cdot 2^{n - 1}$, taken modulo $998244353$.

输出一个数字——$p \cdot 2^{n - 1}$ 对 $998244353$ 取模的结果。