#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
using ld = long double;
template <typename T>
void _(const char* s, T h) {
  cerr << s << " = " << h << "\n";
}
template <typename T, typename... Ts>
void _(const char* s, T h, Ts... t) {
  int b = 0;
  while (((b += *s == '(') -= *s == ')') != 0 || *s != ',') cerr << *s++;
  cerr << " = " << h << ",";
  _(s + 1, t...);
}
struct init {
  init() {
    cin.tie(0);
    iostream::sync_with_stdio(0);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(5);
  }
  ~init() {}
} init;
template <typename T, typename U>
void upx(T& x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
void upn(T& x, U y) {
  if (x > y) x = y;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll D = 4, dx[] = {+1, 0, -1, 0}, dy[] = {0, +1, 0, -1};
const int32_t M = 998244353;
int32_t rev(int32_t x, int32_t m) {
  if (x == 1) return 1;
  return (1 - (ll)rev(m % x, x) * m) / x + m;
}
struct mint {
  int32_t x;
  mint() : x(0) {}
  mint(int32_t xx) : x(xx % M) {
    if (x < 0) x += M;
  }
  mint(ll xx) : x(xx % M) {
    if (x < 0) x += M;
  }
  mint& operator+=(mint b) {
    if ((x += b.x) >= M) x -= M;
    return *this;
  }
  mint operator+(mint b) {
    mint res = *this;
    res += b;
    return res;
  }
  mint& operator-=(mint b) {
    if ((x -= b.x) < 0) x += M;
    return *this;
  }
  mint operator-(mint b) {
    mint res = *this;
    res -= b;
    return res;
  }
  mint& operator*=(mint b) {
    x = (ll)x * b.x % M;
    return *this;
  }
  mint operator*(mint b) {
    mint res = *this;
    res *= b;
    return res;
  }
  mint inverse() { return rev(x, M); }
  mint& operator/=(mint b) {
    x = (ll)x * rev(b.x, M) % M;
    return *this;
  }
  mint operator/(mint b) {
    mint res = *this;
    res /= b;
    return res;
  }
  mint operator^(ll w) {
    mint r = 1, a = *this;
    while (w) {
      if (w & 1) r *= a;
      a *= a;
      w /= 2;
    }
    return r;
  }
  mint operator^=(ll w) { return *this = (*this) ^ w; }
  mint operator^(mint w) { return *this ^ w.x; }
  mint operator^=(mint w) { return *this = (*this) ^ w; }
  mint operator-() const { return mint() - *this; }
  explicit operator bool() const { return x; }
};
istream& operator>>(istream& is, mint& p) {
  istream& res = is >> p.x;
  p.x %= M;
  return res;
}
ostream& operator<<(ostream& os, mint p) { return os << p.x; }
template <typename T>
mint operator+(T x, mint y) {
  return mint(x) + y;
}
template <typename T>
mint operator-(T x, mint y) {
  return mint(x) - y;
}
template <typename T>
mint operator*(T x, mint y) {
  return mint(x) * y;
}
template <typename T>
mint operator/(T x, mint y) {
  return mint(x) / y;
}
template <typename T>
mint operator^(T x, mint y) {
  return mint(x) ^ y;
}
mint abs(mint x) { return x; }
const ll N = 505050;
struct md {
  mint a, b;
  bool first;
} mod[N * 4];
mint t[N * 4], len[N * 4];
ll sh = 1;
void apply(ll v, md m) {
  if (m.first) {
    t[v] = m.b * len[v];
    mod[v] = m;
  } else {
    (t[v] *= m.a) += m.b * len[v];
    mod[v].a *= m.a;
    (mod[v].b *= m.a) += m.b;
  }
}
void push(ll v) {
  apply(v + v, mod[v]);
  apply(v + v + 1, mod[v]);
  mod[v] = {1, 0, 0};
}
void recalc(ll v) { t[v] = t[v + v] + t[v + v + 1]; }
ll a[N];
ll al[N];
void build(ll n) {
  while (sh < n) sh *= 2;
  for (ll i = 0; i < (sh + sh); ++i) t[i] = 0;
  for (ll i = 0; i < (sh + sh); ++i) mod[i] = {1, 0, 0};
  for (ll i = 0; i < (n); ++i) {
    len[i + sh] = al[i];
    if (i) len[i + sh] -= al[i - 1];
  }
  for (ll i = sh - 1; i > 0; --i) len[i] = len[i + i] + len[i + i + 1];
}
ll l, r;
md m;
void upd(ll v, ll tl, ll tr) {
  if (l <= tl && tr <= r) {
    apply(v, m);
    return;
  }
  push(v);
  ll tm = (tl + tr) / 2;
  if (tm >= l) upd(v + v, tl, tm);
  if (tm + 1 <= r) upd(v + v + 1, tm + 1, tr);
  recalc(v);
}
void upd(ll _l, ll _r, md _m) {
  if (_l > _r) return;
  l = _l, r = _r, m = _m;
  upd(1, 0, sh - 1);
}
int32_t main() {
  ll n;
  cin >> n;
  for (ll i = 0; i < (n); ++i) {
    cin >> a[i];
    al[i] = a[i];
  }
  sort(al, al + n);
  ll m = unique(al, al + n) - al;
  build(m);
  ll ap = lower_bound(al, al + m, a[0]) - al;
  upd(0, ap, md{0, 1, 1});
  for (ll i = 1; i < n; ++i) {
    ll ai = lower_bound(al, al + m, a[i]) - al;
    mint tot = t[1];
    upd(0, ai, md{-1, tot, 0});
    upd(ai + 1, sh - 1, md{0, 0, 0});
    ap = ai;
  }
  cout << t[1] << '\n';
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
using ll = long long;
using uint = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
using ld = long double;
template <typename T>
void _(const char* s, T h) {
  cerr << s << " = " << h << "\n";
}
template <typename T, typename... Ts>
void _(const char* s, T h, Ts... t) {
  int b = 0;
  while (((b += *s == '(') -= *s == ')') != 0 || *s != ',') cerr << *s++;
  cerr << " = " << h << ",";
  _(s + 1, t...);
}
struct init {
  init() {
    cin.tie(0);
    iostream::sync_with_stdio(0);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(5);
  }
  ~init() {}
} init;
template <typename T, typename U>
void upx(T& x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
void upn(T& x, U y) {
  if (x > y) x = y;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll D = 4, dx[] = {+1, 0, -1, 0}, dy[] = {0, +1, 0, -1};
const int32_t M = 998244353;
int32_t rev(int32_t x, int32_t m) {
  if (x == 1) return 1;
  return (1 - (ll)rev(m % x, x) * m) / x + m;
}
struct mint {
  int32_t x;
  mint() : x(0) {}
  mint(int32_t xx) : x(xx % M) {
    if (x < 0) x += M;
  }
  mint(ll xx) : x(xx % M) {
    if (x < 0) x += M;
  }
  mint& operator+=(mint b) {
    if ((x += b.x) >= M) x -= M;
    return *this;
  }
  mint operator+(mint b) {
    mint res = *this;
    res += b;
    return res;
  }
  mint& operator-=(mint b) {
    if ((x -= b.x) < 0) x += M;
    return *this;
  }
  mint operator-(mint b) {
    mint res = *this;
    res -= b;
    return res;
  }
  mint& operator*=(mint b) {
    x = (ll)x * b.x % M;
    return *this;
  }
  mint operator*(mint b) {
    mint res = *this;
    res *= b;
    return res;
  }
  mint inverse() { return rev(x, M); }
  mint& operator/=(mint b) {
    x = (ll)x * rev(b.x, M) % M;
    return *this;
  }
  mint operator/(mint b) {
    mint res = *this;
    res /= b;
    return res;
  }
  mint operator^(ll w) {
    mint r = 1, a = *this;
    while (w) {
      if (w & 1) r *= a;
      a *= a;
      w /= 2;
    }
    return r;
  }
  mint operator^=(ll w) { return *this = (*this) ^ w; }
  mint operator^(mint w) { return *this ^ w.x; }
  mint operator^=(mint w) { return *this = (*this) ^ w; }
  mint operator-() const { return mint() - *this; }
  explicit operator bool() const { return x; }
};
istream& operator>>(istream& is, mint& p) {
  istream& res = is >> p.x;
  p.x %= M;
  return res;
}
ostream& operator<<(ostream& os, mint p) { return os << p.x; }
template <typename T>
mint operator+(T x, mint y) {
  return mint(x) + y;
}
template <typename T>
mint operator-(T x, mint y) {
  return mint(x) - y;
}
template <typename T>
mint operator*(T x, mint y) {
  return mint(x) * y;
}
template <typename T>
mint operator/(T x, mint y) {
  return mint(x) / y;
}
template <typename T>
mint operator^(T x, mint y) {
  return mint(x) ^ y;
}
mint abs(mint x) { return x; }
const ll N = 505050;
struct md {
  mint a, b;
  bool first;
} mod[N * 4];
mint t[N * 4], len[N * 4];
ll sh = 1;
void apply(ll v, md m) {
  if (m.first) {
    t[v] = m.b * len[v];
    mod[v] = m;
  } else {
    (t[v] *= m.a) += m.b * len[v];
    mod[v].a *= m.a;
    (mod[v].b *= m.a) += m.b;
  }
}
void push(ll v) {
  apply(v + v, mod[v]);
  apply(v + v + 1, mod[v]);
  mod[v] = {1, 0, 0};
}
void recalc(ll v) { t[v] = t[v + v] + t[v + v + 1]; }
ll a[N];
ll al[N];
void build(ll n) {
  while (sh < n) sh *= 2;
  for (ll i = 0; i < (sh + sh); ++i) t[i] = 0;
  for (ll i = 0; i < (sh + sh); ++i) mod[i] = {1, 0, 0};
  for (ll i = 0; i < (n); ++i) {
    len[i + sh] = al[i];
    if (i) len[i + sh] -= al[i - 1];
  }
  for (ll i = sh - 1; i > 0; --i) len[i] = len[i + i] + len[i + i + 1];
}
ll l, r;
md m;
void upd(ll v, ll tl, ll tr) {
  if (l <= tl && tr <= r) {
    apply(v, m);
    return;
  }
  push(v);
  ll tm = (tl + tr) / 2;
  if (tm >= l) upd(v + v, tl, tm);
  if (tm + 1 <= r) upd(v + v + 1, tm + 1, tr);
  recalc(v);
}
void upd(ll _l, ll _r, md _m) {
  if (_l > _r) return;
  l = _l, r = _r, m = _m;
  upd(1, 0, sh - 1);
}
int32_t main() {
  ll n;
  cin >> n;
  for (ll i = 0; i < (n); ++i) {
    cin >> a[i];
    al[i] = a[i];
  }
  sort(al, al + n);
  ll m = unique(al, al + n) - al;
  build(m);
  ll ap = lower_bound(al, al + m, a[0]) - al;
  upd(0, ap, md{0, 1, 1});
  for (ll i = 1; i < n; ++i) {
    ll ai = lower_bound(al, al + m, a[i]) - al;
    mint tot = t[1];
    upd(0, ai, md{-1, tot, 0});
    upd(ai + 1, sh - 1, md{0, 0, 0});
    ap = ai;
  }
  cout << t[1] << '\n';
  return 0;
}

```