#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
inline int add(int a, int b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
inline void inc(int &a, int b) { a = add(a, b); }
inline int sub(int a, int b) { return (a - b < 0) ? a - b + MOD : a - b; }
inline void dec(int &a, int b) { a = sub(a, b); }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }
inline void grow(int &a, int b) { a = mul(a, b); }
struct node {
  int sum, tl, tr, a, b;
  node *l, *r;
  node(int _sum, int _tl, int _tr, int _a = 1, int _b = 0) {
    sum = _sum, tl = _tl, tr = _tr, a = _a, b = _b;
    l = nullptr;
    r = nullptr;
  }
  void push() {
    if (tl != tr) {
      if (!l) {
        int tm = (tl + tr) >> 1;
        l = new node(sum, tl, tm);
        r = new node(sum, tm + 1, tr);
      }
      grow(l->a, a);
      l->b = add(mul(a, l->b), b);
      grow(r->a, a);
      r->b = add(mul(a, r->b), b);
    }
    sum = add(mul(a, sum), mul(b, (tr - tl + 1) % MOD));
    a = 1, b = 0;
  }
  void upd(int l, int r, int na, int nb) {
    push();
    if (tr < l || tl > r) return;
    if (l <= tl && tr <= r) {
      grow(a, na);
      b = add(mul(na, b), nb);
      push();
      return;
    }
    this->l->upd(l, r, na, nb);
    this->r->upd(l, r, na, nb);
    sum = add(this->l->sum, this->r->sum);
  }
};
node *root = new node(0, 1, 1000000000);
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int b;
    cin >> b;
    root->upd(1, b, MOD - 1, i ? root->sum : 1);
    root->upd(b + 1, 1000000000, 0, 0);
  }
  cout << root->sum << '\n';
}

### Prompt

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

You are given an array of n positive integers a_1, a_2, …, a_n. Your task is to calculate the number of arrays of n positive integers b_1, b_2, …, b_n such that: 

  * 1 ≤ b_i ≤ a_i for every i (1 ≤ i ≤ n), and 
  * b_i ≠ b_{i+1} for every i (1 ≤ i ≤ n - 1). 



The number of such arrays can be very large, so print it modulo 998 244 353.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the array a.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9).

Output

Print the answer modulo 998 244 353 in a single line.

Examples

Input


3
2 2 2


Output


2

Input


2
2 3


Output


4

Input


3
1 1 1


Output


0

Note

In the first test case possible arrays are [1, 2, 1] and [2, 1, 2].

In the second test case possible arrays are [1, 2], [1, 3], [2, 1] and [2, 3].

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
inline int add(int a, int b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
inline void inc(int &a, int b) { a = add(a, b); }
inline int sub(int a, int b) { return (a - b < 0) ? a - b + MOD : a - b; }
inline void dec(int &a, int b) { a = sub(a, b); }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }
inline void grow(int &a, int b) { a = mul(a, b); }
struct node {
  int sum, tl, tr, a, b;
  node *l, *r;
  node(int _sum, int _tl, int _tr, int _a = 1, int _b = 0) {
    sum = _sum, tl = _tl, tr = _tr, a = _a, b = _b;
    l = nullptr;
    r = nullptr;
  }
  void push() {
    if (tl != tr) {
      if (!l) {
        int tm = (tl + tr) >> 1;
        l = new node(sum, tl, tm);
        r = new node(sum, tm + 1, tr);
      }
      grow(l->a, a);
      l->b = add(mul(a, l->b), b);
      grow(r->a, a);
      r->b = add(mul(a, r->b), b);
    }
    sum = add(mul(a, sum), mul(b, (tr - tl + 1) % MOD));
    a = 1, b = 0;
  }
  void upd(int l, int r, int na, int nb) {
    push();
    if (tr < l || tl > r) return;
    if (l <= tl && tr <= r) {
      grow(a, na);
      b = add(mul(na, b), nb);
      push();
      return;
    }
    this->l->upd(l, r, na, nb);
    this->r->upd(l, r, na, nb);
    sum = add(this->l->sum, this->r->sum);
  }
};
node *root = new node(0, 1, 1000000000);
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int b;
    cin >> b;
    root->upd(1, b, MOD - 1, i ? root->sum : 1);
    root->upd(b + 1, 1000000000, 0, 0);
  }
  cout << root->sum << '\n';
}

```