{"problem":{"name":"E. Intercity Travelling","description":{"content":"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 (","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1009E"},"statements":[{"statement_type":"Markdown","content":"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.\n\nThe 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.\n\nDriving 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.\n\nFortunately, 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.\n\nFor 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$.\n\nLeha 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.\n\nObviously, $p \\cdot 2^{n - 1}$ is an integer number. You have to calculate it modulo $998244353$.\n\n## Input\n\nThe first line contains one number $n$ ($1 \\le n \\le 10^6$) — the distance from Moscow to Saratov.\n\nThe 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\n## Output\n\nPrint one number — $p \\cdot 2^{n - 1}$, taken modulo $998244353$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Leha 计划从莫斯科前往萨拉托夫。他讨厌火车，因此决定开车从一个城市到另一个城市。\n\n莫斯科到萨拉托夫的路径可以表示为一条直线（尽管现实中并非如此笔直，但在本题中我们将其视为直线），两地之间的距离为 $n$ 公里。设莫斯科位于坐标 $0$ 公里处，萨拉托夫位于坐标 $n$ 公里处。\n\n长时间驾驶可能非常困难。形式上，如果 Leha 自上次休息后已行驶了 $i$ 公里，则他将第 $(i + 1)$ 公里的困难度视为 $a_{i + 1}$。保证对于每个 $i \\in [1, n - 1]$，都有 $a_i \\leq a_{i + 1}$。旅程的困难度定义为旅程中每公里困难度的总和。\n\n幸运的是，莫斯科与萨拉托夫之间可能存在一些休息点。每个从 $1$ 到 $n - 1$ 的整数点都可能有一个休息点。当 Leha 进入一个休息点时，他可以休息，此时下一公里的困难度变为 $a_1$，再下一公里为 $a_2$，依此类推。\n\n例如，若 $n = 5$ 且坐标 $2$ 处有一个休息点，则旅程的困难度为 $2 a_1 + 2 a_2 + a_3$：第一公里困难度为 $a_1$，第二公里为 $a_2$，之后 Leha 休息，第三公里困难度为 $a_1$，第四公里为 $a_2$，最后一公里为 $a_3$。另一个例子：若 $n = 7$ 且坐标 $1$ 和 $5$ 处有休息点，则 Leha 旅程的困难度为 $3 a_1 + 2 a_2 + a_3 + a_4$。\n\nLeha 不知道哪些整数点有休息点。因此他必须考虑所有可能的情况。显然，休息点的分布共有 $2^{n - 1}$ 种（两种分布不同当且仅当存在某个点 $x$，使得它在其中一种分布中有休息点而在另一种中没有）。Leha 认为所有这些分布都是等概率的。他希望计算 $p$ —— 他旅程困难度的期望值。\n\n显然，$p \\cdot 2^{n - 1}$ 是一个整数。你需要计算它对 $998244353$ 取模的结果。\n\n第一行包含一个数 $n$（$1 \\leq n \\leq 10^6$）—— 从莫斯科到萨拉托夫的距离。\n\n第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$（$1 \\leq a_1 \\leq a_2 \\leq \\dots \\leq a_n \\leq 10^6$），其中 $a_i$ 表示 Leha 休息后第 $i$ 公里的困难度。\n\n输出一个数 —— $p \\cdot 2^{n - 1}$ 对 $998244353$ 取模的结果。\n\n## Input\n\n第一行包含一个数 $n$（$1 \\leq n \\leq 10^6$）—— 从莫斯科到萨拉托夫的距离。\n\n第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$（$1 \\leq a_1 \\leq a_2 \\leq \\dots \\leq a_n \\leq 10^6$），其中 $a_i$ 表示 Leha 休息后第 $i$ 公里的困难度。\n\n## Output\n\n输出一个数 —— $p \\cdot 2^{n - 1}$ 对 $998244353$ 取模的结果。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the total distance (in km) from Moscow (coordinate 0) to Saratov (coordinate $ n $).  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a non-decreasing sequence of positive integers, where $ a_i $ is the difficulty of the $ i $-th kilometer after a rest.\n\nLet $ \\mathcal{S} $ be the set of all $ 2^{n-1} $ possible subsets of rest sites, where each rest site is located at an integer coordinate $ x \\in \\{1, 2, \\dots, n-1\\} $.  \nFor each subset $ R \\in \\mathcal{S} $, define the journey difficulty $ D(R) $ as the sum of difficulties over all $ n $ kilometers, with the difficulty of the $ j $-th kilometer after the most recent rest (or start) being $ a_k $, where $ k $ is the number of kilometers traveled since the last rest (or from the start).\n\nLet $ P = \\sum_{R \\in \\mathcal{S}} D(R) $ be the total difficulty over all possible rest site configurations.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^6 $  \n2. $ 1 \\leq a_1 \\leq a_2 \\leq \\dots \\leq a_n \\leq 10^6 $\n\n**Objective**  \nCompute $ P \\mod 998244353 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1009E","tags":["combinatorics","math","probabilities"],"sample_group":[["2\n1 2","5"],["4\n1 3 3 7","60"]],"created_at":"2026-03-03 11:00:39"}}