← 返回题目列表

Codeforces · 1009/E

E. 城际旅行

中文机器翻译题面 查看原题

Leha 正在计划从莫斯科到萨拉托夫的旅程。他讨厌火车,所以他决定乘汽车从一个城市到另一个城市。

从莫斯科到萨拉托夫的路径可以表示为一条直线(实际上并不是那么直,但在这个问题中我们将认为它是直的),莫斯科和萨拉托夫之间的距离是 $$$n$$$ km。假设莫斯科位于坐标 $$$0$$$ km 的点,而萨拉托夫位于坐标 $$$n$$$ km 的点。

长时间驾驶可能真的很困难。正式来说,如果 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$$$都有休息点,则Leha旅程的难度为$$$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$$$, ..., $$$a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^6$$$),其中 $$$a_i$$$ 是 $$$i$$$-th 的难度Leha 休息后一公里。

输出

打印一个数字 — $$$p \cdot 2^{n - 1}$$$,以 $$$998244353$$$ 为模。

示例

输入 #1

2
1 2

输出 #1

5

输入 #2

4
1 3 3 7

输出 #2

60