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: HARD
Tags: Combinatorics

Mathematics

Probability
Expected Time Complexity: O(N)

Starter code:

Solutions:
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()


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)


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))
main()


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
MOD = 998244353
ans = 0
pow_ = 1
for i in range(n):
	if i == 0:
		ans += a[n - i - 1]
		ans %= MOD
	else:
		pow_ = pow_ * 2 * (i + 2) * pow(i + 1, MOD - 2, MOD)
		pow_ %= MOD
		ans += a[n - i - 1] * pow_
		ans %= MOD
print(ans)


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 = [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)


M = 998244353
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 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 os
import sys
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
a = array()
series = [1]
fact = 1
for i in range(n + 1):
	series.append((series[-1] * 2 % M + fact) % M)
	fact = fact * 2 % M
ind = n - 1
ans = 0
for i in range(n):
	ans = (ans + a[i] * series[ind] % M) % M
	ind -= 1
print(ans)


def some_random_function():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function5():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
import os, sys
from io import BytesIO, IOBase

def main():
	mod = 998244353
	powe = [1]
	for _ in range(10 ** 6):
		powe.append(powe[-1] * 2 % mod)
	n = int(input())
	a = list(map(int, input().split()))
	(ans, dp, dp1) = (a[0] * powe[n - 1] % mod, a[0], 0)
	for i in range(1, n):
		if i == 1:
			dp = (dp + a[i]) % mod
		else:
			dp = (dp * 2 + a[i] - dp1) % mod
		ans = (ans + powe[n - i - 1] * dp) % mod
		dp1 = a[i]
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def some_random_function1():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function2():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function3():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function4():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function6():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function7():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function8():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
main()


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


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


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)
main()


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)


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)


import functools
import time

def timer(func):

	@functools.wraps(func)
	def wrapper(*args, **kwargs):
		stime = time.perf_counter()
		res = func(*args, **kwargs)
		elapsed = time.perf_counter() - stime
		print(f'{func.__name__} in {elapsed:.4f} secs')
		return res
	return wrapper

class solver:

	def __init__(self):
		pass

	def __call__(self):
		MOD = 998244353
		N = 1000007
		pow2 = [0] * N
		n = int(input())
		a = list(map(int, input().strip().split()))
		pow2[0] = 1
		for i in range(n):
			pow2[i + 1] = 2 * pow2[i] % MOD
		res = 0
		for i in range(1, n):
			tmp = a[i - 1] * (n + 2 - i) % MOD
			res += pow2[n - 1 - i] * tmp % MOD
			res %= MOD
		res += a[n - 1]
		res %= MOD
		print(res)
solver()()


from sys import stdin, stdout

def main():
	p = 998244353
	n = int(stdin.readline())
	a = list(readline())
	answer = a[-1]
	pow_ = 1
	for i in range(n - 1, 0, -1):
		answer = (answer + a[i - 1] * (2 + n - i) * pow_ % p) % p
		pow_ = pow_ * 2 % p
	return answer

def readline():
	return map(int, stdin.readline().strip().split())
stdout.write(str(main()) + '\n')


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)


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)


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)


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
print(calc(int(input()), list(map(int, input().split(' ')))))


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[n - 1]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[0]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
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)


from sys import stdin
n = int(input())
a = list(map(int, stdin.readline().split()))
mod = 998244353

def solve(a):
	if len(a) == 1:
		return a[0]
	dp = [0] * n
	dp[0] = a[0]
	dp[1] = a[0] + a[1]
	for i in range(2, len(a)):
		dp[i] = (a[i] + a[i - 1] + (dp[i - 1] - a[i - 1]) * 2) % mod
	for i in range(1, len(a)):
		dp[i] = (2 * dp[i - 1] + dp[i]) % mod
	return dp[-1]
print(solve(a))