#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long MOD2 = 998244353;
const long long BIG = 1197423052705914509LL;
mt19937 rng(
    (long long)std::chrono::steady_clock::now().time_since_epoch().count());
const long long MAXN = 1e5 + 10;
const long long is_query = -BIG;
struct line {
  long long m, b;
  mutable function<const line*()> succ;
  bool operator<(const line& rhs) const {
    if (rhs.b != is_query) return m < rhs.m;
    const line* s = succ();
    if (!s) return 0;
    long long x = rhs.m;
    return b - s->b < (s->m - m) * x;
  }
};
struct dynamic_hull : public multiset<line> {
  const long long inf = BIG;
  bool bad(iterator y) {
    auto z = next(y);
    if (y == begin()) {
      if (z == end()) return 0;
      return y->m == z->m && y->b <= z->b;
    }
    auto x = prev(y);
    if (z == end()) return y->m == x->m && y->b <= x->b;
    long long v1 = (x->b - y->b);
    if (y->m == x->m)
      v1 = x->b > y->b ? inf : -inf;
    else
      v1 /= (y->m - x->m);
    long long v2 = (y->b - z->b);
    if (z->m == y->m)
      v2 = y->b > z->b ? inf : -inf;
    else
      v2 /= (z->m - y->m);
    return v1 >= v2;
  }
  void insert_line(long long m, long long b) {
    auto y = insert({m, b});
    y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
    if (bad(y)) {
      erase(y);
      return;
    }
    while (next(y) != end() && bad(next(y))) erase(next(y));
    while (y != begin() && bad(prev(y))) erase(prev(y));
  }
  long long eval(long long x) {
    auto l = *lower_bound((line){x, is_query});
    return l.m * x + l.b;
  }
};
struct auxiliary_tree {
  long long n;
  vector<long long> ori[MAXN];
  vector<long long> storelatest;
  long long tin[MAXN], tout[MAXN], dep[MAXN], cor[MAXN];
  bool imp[MAXN];
  long long run = 0;
  vector<long long> euler;
  vector<vector<pair<long long, long long> > > lca_table;
  long long lef[MAXN], rig[MAXN];
  void dfs(long long node, long long prev, long long de) {
    dep[node] = de;
    tin[node] = ++run;
    cor[tin[node]] = node;
    euler.push_back(node);
    for (long long i = 0; i < ori[node].size(); i++) {
      if (ori[node][i] != prev) {
        dfs(ori[node][i], node, de + 1);
        euler.push_back(node);
      }
    }
    tout[node] = ++run;
  }
  void find_all_lcas() {
    long long k = log2(2 * n - 1);
    lca_table.resize(k + 1);
    for (long long i = 0; i < k + 1; i++) {
      lca_table[i].resize(2 * n - 1);
    }
    for (long long i = 0; i < 2 * n - 1; i++) {
      lca_table[0][i] = make_pair(dep[euler[i]], euler[i]);
    }
    for (long long i = 1; i <= k; i++) {
      for (long long j = 0; j < 2 * n - 1; j++) {
        if (j + (1 << (i - 1)) >= 2 * n - 1) continue;
        if (lca_table[i - 1][j].first <
            lca_table[i - 1][j + (1 << (i - 1))].first) {
          lca_table[i][j].first = lca_table[i - 1][j].first;
          lca_table[i][j].second = lca_table[i - 1][j].second;
        } else {
          lca_table[i][j].first = lca_table[i - 1][j + (1 << (i - 1))].first;
          lca_table[i][j].second = lca_table[i - 1][j + (1 << (i - 1))].second;
        }
      }
    }
    for (long long i = 0; i < MAXN; i++) lef[i] = -1;
    for (long long i = 0; i < 2 * n - 1; i++) {
      if (lef[euler[i]] == -1) {
        lef[euler[i]] = i;
      }
      rig[euler[i]] = i;
    }
  }
  bool isParent(long long u, long long v) {
    return tin[u] < tin[v] && tout[v] < tout[u];
  }

 public:
  vector<long long> adj[MAXN];
  long long root;
  long long lcadep(long long x, long long y) {
    if (lef[x] > rig[y]) {
      swap(x, y);
    }
    long long k = log2(rig[y] - lef[x] + 1);
    return min(lca_table[k][lef[x]].first,
               lca_table[k][rig[y] - (1 << k) + 1].first);
  }
  long long lcaidx(long long x, long long y) {
    if (lef[x] > rig[y]) {
      swap(x, y);
    }
    long long k = log2(rig[y] - lef[x] + 1);
    if (lca_table[k][lef[x]].first <
        lca_table[k][rig[y] - (1 << k) + 1].first) {
      return lca_table[k][lef[x]].second;
    } else {
      return lca_table[k][rig[y] - (1 << k) + 1].second;
    }
  }
  void base(long long x, long long rt, vector<long long> y[]) {
    n = x;
    for (long long i = 1; i <= n; i++) {
      ori[i] = y[i];
    }
    dfs(rt, -1, 0);
    find_all_lcas();
  }
  void build(vector<long long> g) {
    for (long long i = 0; i < g.size(); i++) {
      g[i] = tin[g[i]];
    }
    sort(g.begin(), g.end());
    for (long long i = 0; i < g.size(); i++) {
      g[i] = cor[g[i]];
    }
    long long k = g.size();
    for (long long i = 0; i < k - 1; i++) {
      g.push_back(lcaidx(g[i], g[i + 1]));
    }
    for (long long i = 0; i < g.size(); i++) {
      g[i] = tin[g[i]];
    }
    sort(g.begin(), g.end());
    for (long long i = 0; i < g.size(); i++) {
      g[i] = cor[g[i]];
    }
    g.erase(unique(g.begin(), g.end()), g.end());
    for (long long i = 0; i < g.size(); i++) {
      imp[g[i]] = 1;
      storelatest.push_back(g[i]);
    }
    stack<long long> vert;
    vert.push(g[0]);
    for (long long i = 1; i < g.size(); i++) {
      long long u = g[i];
      while (vert.size() > 1 && isParent(vert.top(), u) == 0) {
        long long sto = vert.top();
        vert.pop();
        adj[vert.top()].push_back(sto);
      }
      vert.push(u);
    }
    while (vert.size() > 1) {
      long long sto = vert.top();
      vert.pop();
      adj[vert.top()].push_back(sto);
    }
    root = vert.top();
  }
  void clear() {
    for (long long i = 0; i < storelatest.size(); i++) {
      imp[storelatest[i]] = 0;
      adj[storelatest[i]].clear();
    }
    storelatest.clear();
  }
};
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t a) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(a + FIXED_RANDOM);
  }
  template <class T>
  size_t operator()(T a) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    hash<T> x;
    return splitmix64(x(a) + FIXED_RANDOM);
  }
  template <class T, class H>
  size_t operator()(pair<T, H> a) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    hash<T> x;
    hash<H> y;
    return splitmix64(x(a.f) * 37 + y(a.s) + FIXED_RANDOM);
  }
};
template <class T, class H>
using umap = unordered_map<T, H, custom_hash>;
void solve(long long test_case) {
  long long dp[1000001];
  dp[1] = 2, dp[2] = 6;
  for (long long i = 3; i <= 1000000; i++) {
    dp[i] = ((dp[i - 1] - dp[i - 2] + MOD2) * 4) % MOD2;
  }
  long long n;
  cin >> n;
  long long a[n + 1];
  for (long long i = 1; i <= n; i++) cin >> a[i];
  reverse(a + 1, a + n + 1);
  long long ans = 0;
  for (long long i = 1; i <= n; i++) ans = (ans + a[i] * dp[i]) % MOD2;
  cout << (ans * 499122177) % MOD2 << "\n";
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  time_t t = clock();
  srand(time(NULL));
  long long T = 1;
  long long test_case = 1;
  while (T--) {
    solve(test_case);
    test_case++;
  }
  cerr << "Program terminated successfully\n";
  t = clock() - t;
  cerr << "Time used: " << fixed << setprecision(3)
       << (long double)(t * 1.0 / CLOCKS_PER_SEC) << " seconds\n";
}

### Prompt

Your task is to create a cpp solution to the following problem:

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 ∈ [1, n - 1] a_i ≤ 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 ⋅ 2^{n - 1} is an integer number. You have to calculate it modulo 998244353.

Input

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

The second line contains n integer numbers a_1, a_2, ..., a_n (1 ≤ a_1 ≤ a_2 ≤ ... ≤ a_n ≤ 10^6), where a_i is the difficulty of i-th kilometer after Leha has rested.

Output

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

Examples

Input

2
1 2


Output

5


Input

4
1 3 3 7


Output

60

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long MOD2 = 998244353;
const long long BIG = 1197423052705914509LL;
mt19937 rng(
    (long long)std::chrono::steady_clock::now().time_since_epoch().count());
const long long MAXN = 1e5 + 10;
const long long is_query = -BIG;
struct line {
  long long m, b;
  mutable function<const line*()> succ;
  bool operator<(const line& rhs) const {
    if (rhs.b != is_query) return m < rhs.m;
    const line* s = succ();
    if (!s) return 0;
    long long x = rhs.m;
    return b - s->b < (s->m - m) * x;
  }
};
struct dynamic_hull : public multiset<line> {
  const long long inf = BIG;
  bool bad(iterator y) {
    auto z = next(y);
    if (y == begin()) {
      if (z == end()) return 0;
      return y->m == z->m && y->b <= z->b;
    }
    auto x = prev(y);
    if (z == end()) return y->m == x->m && y->b <= x->b;
    long long v1 = (x->b - y->b);
    if (y->m == x->m)
      v1 = x->b > y->b ? inf : -inf;
    else
      v1 /= (y->m - x->m);
    long long v2 = (y->b - z->b);
    if (z->m == y->m)
      v2 = y->b > z->b ? inf : -inf;
    else
      v2 /= (z->m - y->m);
    return v1 >= v2;
  }
  void insert_line(long long m, long long b) {
    auto y = insert({m, b});
    y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
    if (bad(y)) {
      erase(y);
      return;
    }
    while (next(y) != end() && bad(next(y))) erase(next(y));
    while (y != begin() && bad(prev(y))) erase(prev(y));
  }
  long long eval(long long x) {
    auto l = *lower_bound((line){x, is_query});
    return l.m * x + l.b;
  }
};
struct auxiliary_tree {
  long long n;
  vector<long long> ori[MAXN];
  vector<long long> storelatest;
  long long tin[MAXN], tout[MAXN], dep[MAXN], cor[MAXN];
  bool imp[MAXN];
  long long run = 0;
  vector<long long> euler;
  vector<vector<pair<long long, long long> > > lca_table;
  long long lef[MAXN], rig[MAXN];
  void dfs(long long node, long long prev, long long de) {
    dep[node] = de;
    tin[node] = ++run;
    cor[tin[node]] = node;
    euler.push_back(node);
    for (long long i = 0; i < ori[node].size(); i++) {
      if (ori[node][i] != prev) {
        dfs(ori[node][i], node, de + 1);
        euler.push_back(node);
      }
    }
    tout[node] = ++run;
  }
  void find_all_lcas() {
    long long k = log2(2 * n - 1);
    lca_table.resize(k + 1);
    for (long long i = 0; i < k + 1; i++) {
      lca_table[i].resize(2 * n - 1);
    }
    for (long long i = 0; i < 2 * n - 1; i++) {
      lca_table[0][i] = make_pair(dep[euler[i]], euler[i]);
    }
    for (long long i = 1; i <= k; i++) {
      for (long long j = 0; j < 2 * n - 1; j++) {
        if (j + (1 << (i - 1)) >= 2 * n - 1) continue;
        if (lca_table[i - 1][j].first <
            lca_table[i - 1][j + (1 << (i - 1))].first) {
          lca_table[i][j].first = lca_table[i - 1][j].first;
          lca_table[i][j].second = lca_table[i - 1][j].second;
        } else {
          lca_table[i][j].first = lca_table[i - 1][j + (1 << (i - 1))].first;
          lca_table[i][j].second = lca_table[i - 1][j + (1 << (i - 1))].second;
        }
      }
    }
    for (long long i = 0; i < MAXN; i++) lef[i] = -1;
    for (long long i = 0; i < 2 * n - 1; i++) {
      if (lef[euler[i]] == -1) {
        lef[euler[i]] = i;
      }
      rig[euler[i]] = i;
    }
  }
  bool isParent(long long u, long long v) {
    return tin[u] < tin[v] && tout[v] < tout[u];
  }

 public:
  vector<long long> adj[MAXN];
  long long root;
  long long lcadep(long long x, long long y) {
    if (lef[x] > rig[y]) {
      swap(x, y);
    }
    long long k = log2(rig[y] - lef[x] + 1);
    return min(lca_table[k][lef[x]].first,
               lca_table[k][rig[y] - (1 << k) + 1].first);
  }
  long long lcaidx(long long x, long long y) {
    if (lef[x] > rig[y]) {
      swap(x, y);
    }
    long long k = log2(rig[y] - lef[x] + 1);
    if (lca_table[k][lef[x]].first <
        lca_table[k][rig[y] - (1 << k) + 1].first) {
      return lca_table[k][lef[x]].second;
    } else {
      return lca_table[k][rig[y] - (1 << k) + 1].second;
    }
  }
  void base(long long x, long long rt, vector<long long> y[]) {
    n = x;
    for (long long i = 1; i <= n; i++) {
      ori[i] = y[i];
    }
    dfs(rt, -1, 0);
    find_all_lcas();
  }
  void build(vector<long long> g) {
    for (long long i = 0; i < g.size(); i++) {
      g[i] = tin[g[i]];
    }
    sort(g.begin(), g.end());
    for (long long i = 0; i < g.size(); i++) {
      g[i] = cor[g[i]];
    }
    long long k = g.size();
    for (long long i = 0; i < k - 1; i++) {
      g.push_back(lcaidx(g[i], g[i + 1]));
    }
    for (long long i = 0; i < g.size(); i++) {
      g[i] = tin[g[i]];
    }
    sort(g.begin(), g.end());
    for (long long i = 0; i < g.size(); i++) {
      g[i] = cor[g[i]];
    }
    g.erase(unique(g.begin(), g.end()), g.end());
    for (long long i = 0; i < g.size(); i++) {
      imp[g[i]] = 1;
      storelatest.push_back(g[i]);
    }
    stack<long long> vert;
    vert.push(g[0]);
    for (long long i = 1; i < g.size(); i++) {
      long long u = g[i];
      while (vert.size() > 1 && isParent(vert.top(), u) == 0) {
        long long sto = vert.top();
        vert.pop();
        adj[vert.top()].push_back(sto);
      }
      vert.push(u);
    }
    while (vert.size() > 1) {
      long long sto = vert.top();
      vert.pop();
      adj[vert.top()].push_back(sto);
    }
    root = vert.top();
  }
  void clear() {
    for (long long i = 0; i < storelatest.size(); i++) {
      imp[storelatest[i]] = 0;
      adj[storelatest[i]].clear();
    }
    storelatest.clear();
  }
};
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t a) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(a + FIXED_RANDOM);
  }
  template <class T>
  size_t operator()(T a) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    hash<T> x;
    return splitmix64(x(a) + FIXED_RANDOM);
  }
  template <class T, class H>
  size_t operator()(pair<T, H> a) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    hash<T> x;
    hash<H> y;
    return splitmix64(x(a.f) * 37 + y(a.s) + FIXED_RANDOM);
  }
};
template <class T, class H>
using umap = unordered_map<T, H, custom_hash>;
void solve(long long test_case) {
  long long dp[1000001];
  dp[1] = 2, dp[2] = 6;
  for (long long i = 3; i <= 1000000; i++) {
    dp[i] = ((dp[i - 1] - dp[i - 2] + MOD2) * 4) % MOD2;
  }
  long long n;
  cin >> n;
  long long a[n + 1];
  for (long long i = 1; i <= n; i++) cin >> a[i];
  reverse(a + 1, a + n + 1);
  long long ans = 0;
  for (long long i = 1; i <= n; i++) ans = (ans + a[i] * dp[i]) % MOD2;
  cout << (ans * 499122177) % MOD2 << "\n";
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  time_t t = clock();
  srand(time(NULL));
  long long T = 1;
  long long test_case = 1;
  while (T--) {
    solve(test_case);
    test_case++;
  }
  cerr << "Program terminated successfully\n";
  t = clock() - t;
  cerr << "Time used: " << fixed << setprecision(3)
       << (long double)(t * 1.0 / CLOCKS_PER_SEC) << " seconds\n";
}

```