Problem 6F. 我爱上课

Problem 6F. 我爱上课

Problem 6F. 我爱上课

时间限制:1s

空间限制:256MB

Description

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

比如,zmszms 的宿舍和教室之间的距离是 nn\rightarrow 我们认为 zmszms 的宿舍位于坐标 00 处,教室位于坐标 nn 处。

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

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

幸好,在教室和宿舍之间 可能 有一些休息点。从 11n1n - 1 的每一个整数点都 可能 包含一个休息点。

zmszms 进入休息点时,由于他比较怕累,所以将会休息一下,那么下一米的难度将会为 a1a_1 ,再下一米的难度为 a2a_2 ,以此类推。


例如,如果 n=5n = 5 和坐标 22 上有一个休息点,那么行程的难度将是 2a1+2a2+a32a_1 + 2a_2 + a_3 : 第一公里的难度为 a1a_1 ,第二公里的难度为 a2a_2 ,然后 zmszms 休息,第三公里的难度为 a1a_1 ,第四公里的难度为 a2a_2 ,最后一公里的难度为 a3a_3

再比如,如果 n=7n = 7 ,坐标 1155 有休息点,zmszms 的旅程难度为 3a1+2a2+a3+a43a_1 + 2a_2 + a_3 + a_4

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

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

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

显然, p2n1p \cdot 2^{n - 1} 是一个整数。你的任务是计算它对 998244353998244353 取模。

Input Format

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

第二行包含 nn 整数 a1a_1a2a_2 ,…, ana_n ( 1a1a2an1061 \le a_1 \le a_2 \le \dots \le a_n \le 10^6 ),其中 aia_izmszms 休息后第 ii 米的难度。

Output Format

打印一个数字 \rightarrow p2n1p \cdot 2^{n - 1} ,并对 998244353998244353 取模。

Input Example #1:

2
1 2

Output Example #1:

Input Example #2:

4
1 3 3 7

Output Example #2:

60

Data Range

1n1061 \le n \le 10^61a1a2an1061 \le a_1 \le a_2 \le \dots \le a_n \le 10^6

信息

ID
1548
难度
9
分类
(无)
标签
(无)
递交数
2
已通过
1
通过率
50%
上传者

相关

在下列训练计划中:

2023秋 悬赏令题单

在下列比赛中:

2023秋 悬赏令第六周