CF1009E Intercity Travelling

Leha 正在计划从莫斯科到萨拉托夫的旅程。他讨厌火车，所以决定开车从一个城市到另一个城市。 从莫斯科到萨拉托夫的路线可以看作是一条直线（虽然实际上并不是很直，但在本题中我们认为它是直线），两地之间的距离为 $n$ 千米。假设莫斯科位于坐标 $0$ 千米处，萨拉托夫位于坐标 $n$ 千米处。 长时间驾驶可能非常辛苦。具体来说，如果 Leha 自上一次休息后已经连续行驶了 $i$ 千米，那么他认为接下来第 $i+1$ 千米的难度为 $a_{i+1}$。保证对于每个 $i \in [1, n-1]$，都有 $a_i \le a_{i+1}$。旅程的总难度定义为每一千米的难度之和。 幸运的是，在莫斯科和萨拉托夫之间可能有一些休息站。每一个从 $1$ 到 $n-1$ 的整数点都可能有一个休息站。当 Leha 到达休息站并休息后，接下来的第一千米难度为 $a_1$，第二千米难度为 $a_2$，以此类推。 例如，如果 $n=5$，在坐标 $2$ 处有一个休息站，则旅程的总难度为 $2a_1 + 2a_2 + a_3$：第一千米难度为 $a_1$，第二千米难度为 $a_2$，然后 Leha 休息，第三千米难度为 $a_1$，第四千米难度为 $a_2$，最后一千米难度为 $a_3$。再如：如果 $n=7$，在坐标 $1$ 和 $5$ 处有休息站，则旅程的总难度为 $3a_1 + 2a_2 + a_3 + a_4$。 Leha 并不知道哪些整数点有休息站，所以他必须考虑所有可能的情况。显然，休息站的分布有 $2^{n-1}$ 种不同的方案（如果存在某个点 $x$，在两个方案中恰好只有一个包含休息站，则这两个方案不同）。Leha 认为所有这些分布是等概率的。他想计算 $p$——旅程难度的期望值。 显然，$p \cdot 2^{n-1}$ 是一个整数。你需要计算它对 $998244353$ 取模的结果。

第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示莫斯科到萨拉托夫的距离。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^6$），其中 $a_i$ 表示 Leha 休息后第 $i$ 千米的难度。

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

由 ChatGPT 4.1 翻译