Problem 6F. 我爱上课

时间限制：1s

空间限制：256MB

Description

显然，我们把从宿舍到教室的路径表示为一条直线，这样我们就可以方便地计算宿舍和教室之间的距离。

比如，\(zms\) 的宿舍和教室之间的距离是 \(n\) 米 \(\rightarrow\) 我们认为 \(zms\) 的宿舍位于坐标 \(0\) 处，教室位于坐标 \(n\) 处。

但是，长时间走路太累了。如果 \(zms\) 自从上次停下来休息后已经又走了 \(i\) 米，他认为走第 \((i + 1)\) 公里的难度为 \(a_{i + 1}\) 。

保证任意 \(i \in [1, n - 1]\) \(a_i \le a_{i + 1}\) 。去上课的难度用走路过程中每米的难度之和表示。

幸好，在教室和宿舍之间 可能 有一些休息点。从 \(1\) 到 \(n - 1\) 的每一个整数点都 可能 包含一个休息点。

当 \(zms\) 进入休息点时，由于他比较怕累，所以将会休息一下，那么下一米的难度将会为 \(a_1\) ，再下一米的难度为 \(a_2\) ，以此类推。

---

例如，如果 \(n = 5\) 和坐标 \(2\) 上有一个休息点，那么行程的难度将是 \(2a_1 + 2a_2 + a_3\) : 第一公里的难度为 \(a_1\) ，第二公里的难度为 \(a_2\) ，然后 \(zms\) 休息，第三公里的难度为 \(a_1\) ，第四公里的难度为 \(a_2\) ，最后一公里的难度为 \(a_3\) 。

再比如，如果 \(n = 7\) ，坐标 \(1\) 和 \(5\) 有休息点，\(zms\) 的旅程难度为 \(3a_1 + 2a_2 + a_3 + a_4\) 。

但是， \(zms\) 不知道哪个整数点包含休息点。所以他必须考虑所有可能的情况。

显然，有 \(2^{n - 1}\) 个不同的休息点分布（ 如果存在某个点 \(x\) ，使得它恰好在其中一个分布中包含休息点，则两个分布是不同的 ）。

\(zms\) 认为所有这些分布都是等概率的。他想计算期望 \(p\) \(\rightarrow\) 他上课途中困难的预期值。

显然， \(p \cdot 2^{n - 1}\) 是一个整数。你的任务是计算它对 \(998244353\) 取模。

Input Format

第一行包含一个数字 \(n\) ( \(1 \le n \le 10^6\) ) \(\rightarrow\) 从 \(zms\) 宿舍到教室的距离。

第二行包含 \(n\) 整数 \(a_1\) ， \(a_2\) ，…， \(a_n\) ( \(1 \le a_1 \le a_2 \le \dots \le a_n \le 10^6\) )，其中 \(a_i\) 为 \(zms\) 休息后第 \(i\) 米的难度。

Output Format

打印一个数字 \(\rightarrow\) \(p \cdot 2^{n - 1}\) ，并对 \(998244353\) 取模。

Input Example #1：

2
1 2

Output Example #1：

5

Input Example #2：

4
1 3 3 7

Output Example #2：

60

Data Range

\(1 \le n \le 10^6\)，\(1 \le a_1 \le a_2 \le \dots \le a_n \le 10^6\) 。