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 (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.

Driving 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.

Fortunately, 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.

For 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$.

Leha 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.

Obviously, $p \cdot 2^{n - 1}$ is an integer number. You have to calculate it modulo $998244353$.


-----Input-----

The first line contains one number $n$ ($1 \le n \le 10^6$) — the distance from Moscow to Saratov.

The 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.


-----Output-----

Print one number — $p \cdot 2^{n - 1}$, taken modulo $998244353$.


-----Examples-----
Input
2
1 2

Output
5

Input
4
1 3 3 7

Output
60

Difficulty: interview

Starter code:

Solutions:
M = 0x3b800001
wa = 0;
n = int(input())
a = list(map(int, input().split()))
now = 1
wa += a[-1]
for i in range(n - 1)[::-1]:
    wa += (now * (n - i - 1) + now * 2) * a[i]
    wa %= M
    now *= 2
    now %= M
print(wa % M)


MOD = 998244353

def main():
    n = int(input())
    a = [int(x) for x in input().split(' ')]
    
    p, sp, s, ss = 0, 0, 0, 0
    for x in a:
        ss = (2 * ss + s) % MOD
        s = (s + x) % MOD
        p = (ss + sp + s) % MOD
        sp = (sp + p) % MOD
    print(p)

def __starting_point():
    main()

__starting_point()

n = int(input())
ans = 0
mod = 998244353
a = list(map(int, input().split()))
p = 1 / 2

for i in range(n):
    ans = (ans + (i + 2) * (p * a[n - i - 1] % mod) % mod) % mod
    p = (2 * p) % mod

print(int(ans) % mod)

n = int(input())
a = list(map(int, input().split()))


s = a[0] % 998244353
y = a[0]
for x in a[1:]:

	s = s * 2 + y + x
	y = y * 2 + x

	s %= 998244353
	y %= 998244353


	# print(s)

# print(a)
# print(c)

print(s)


n = int(input())
a = [int(x) for x in input().strip().split()]
mod = 998244353
ans = 0

g = [1, 2]
p = 1

while len(g) < n:
    h = g[-1] * 2 + p
    p *= 2
    if p > mod:
        p %= mod
    if h > mod:
        h %= mod
    g.append(h)

for i in range(n):
    if i > 0:
        a[i] = (a[i] + a[i - 1]) % mod
    ans += a[i] * g[n-1-i]
    if ans > mod:
        ans %= mod

print(ans)


n = int(input())
data = list(map(int,input().split()))

answer = 0

prefix_data_sum = 0
prefix_answer_sum = 0
prefix = 0
mod = 998244353

for i in range(n):
    prefix+=data[i]
    prefix %= mod
    answer = (prefix + prefix_data_sum + prefix_answer_sum) % mod

    prefix_data_sum *= 2
    
    prefix_data_sum = (prefix_data_sum + prefix) % mod
    
    
    prefix_answer_sum = (prefix_answer_sum + answer) % mod
    

print(answer)


def main():
    input()
    s, *aa = list(map(int, input().split()))
    y = s
    for a in aa:
        s = (s * 2 + y + a) % 998244353
        y = (y * 2 + a) % 998244353
    print(s)


def __starting_point():
    main()

__starting_point()

n = int(input())
a=  list(map(int,input().split()))
sum, cur = a[0] % 998244353, a[0]

for x in a[1:]:
    sum  = sum * 2 + cur + x
    cur = cur * 2 + x
    sum %= 998244353
    cur %= 998244353
print(sum)

3

MOD = 998244353

def solve(N, A):
    ans = 0

    k = 1
    ans += k * A[-1]
    ans %= MOD

    for i in range(N - 2, -1, -1):
        ans += k * (N + 1 - i) * A[i]
        ans %= MOD
        k *= 2
        k %= MOD

    return ans


def main():
    N = int(input())
    A = [int(e) for e in input().split(' ')]
    assert len(A) == N
    print(solve(N, A))


def __starting_point():
    main()

__starting_point()

n = int(input())
a=  list(map(int,input().split()))
sum, cur = a[0] % 998244353, a[0]

for x in a[1:]:
    sum  = sum * 2 + cur + x
    cur = cur * 2 + x
    sum %= 998244353
    cur %= 998244353
print(sum)

n = int(input())
a = list(map(int, input().split()))
difficulty = a[0]
expectation = a[0] % 998244353
for i in range(1, n):
    expectation = expectation * 2 + difficulty + a[i]
    difficulty = difficulty * 2 + a[i]
    expectation %= 998244353
    difficulty %= 998244353
print(expectation)


a = int(input())
b = list(map(int,input().split()))
c = b[0]%998244353
d = b[0]%998244353
for i in range(1,a):
    c = (2*c + d + b[i])%998244353
    d = (2*d + b[i])%998244353
print(c)

i,m=input,998244353
i()
a=map(int,i().split())
r,c=[next(a)]*2
for j in a:r,c=(2*r+c+j)%m,(2*c+j)%m
print(r)

mod = 998244353

def calc(nn, costs):
  total = costs[-1]
  mult = 1
  for a in range(nn-1, 0, -1):
    total = (total + ((costs[a - (nn+1)] * mult) % mod) * (nn - a + 2) % mod) % mod
    mult = (mult * 2) % mod
  return total


# calc(1000000, [1000000 for a in range(1000000)])
print(calc(int(input()), list(map(int, input().split(" ")))))

def main():
  n=int(input())
  a=list(map(int,input().split()))
  if n==1:print(a[0]);return
  mod=998244353
  for i in range(1,n):a[i]+=a[i-1]
  ans=0
  for i in range(n-2):
    m=(n-1)-(i+2)
    ans=(ans+pow(2,m,mod)*a[i]*(m+5))%mod
  print((ans+a[-2]+a[-2]+a[-1])%mod)

def __starting_point():
  main()
__starting_point()

MOD=998244353
def f(n):
    if(n==0):
        return 1
    if(n==1):
        return 3
    return ((n+2)*pow(2,n-1,MOD))%MOD
n=int(input())
ar=list(map(int,input().split()))[::-1]
S=0
for i in range(n):
    S+=ar[i]*f(i)
print(S%MOD)


import sys
input=sys.stdin.readline


n=int(input())
a=list(map(int,input().split()))
m=998244353
a=a[::-1]
s=a[0]
for i in range(1,n):
    s+=(a[i]*pow(2,i-1,m)*(i+2))%m
    s=s%m
print(s%m)