#include <bits/stdc++.h>
long long read() {
  long long x = 0, f = 1;
  int c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
  return f * x;
}
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
template <typename T>
bool umin(T& a, T t) {
  if (a > t) return a = t, 1;
  return 0;
}
template <typename T>
bool umax(T& a, T t) {
  if (a < t) return a = t, 1;
  return 0;
}
const int MAXN = 525011, mod = 998244353, inv2 = (mod + 1) >> 1;
const int INF = 1e9 + 233;
long long Qpow(long long a, long long p) {
  if (a == 2 && p == mod - 2) return inv2;
  long long res = 1;
  while (p) {
    if (p & 1) res = res * a % mod;
    a = a * a % mod, p >>= 1;
  }
  return res;
}
struct Mint {
  int x;
  Mint() : x(0) {}
  Mint(long long x) : x((0 <= x && x < mod ? x : (x % mod + mod) % mod)) {}
  void operator+=(Mint you) {
    x += you.x;
    if (x >= mod) x -= mod;
  }
  void operator-=(Mint you) {
    x -= you.x;
    if (x < 0) x += mod;
  }
  void operator*=(Mint you) { x = long long(x) * you.x % mod; }
  void operator/=(Mint you) { x = long long(x) * Qpow(you.x, mod - 2) % mod; }
  Mint operator-() { return x ? mod - x : 0; }
  Mint Inv() { return Qpow(x, mod - 2); }
};
Mint operator+(Mint a, Mint b) {
  int t = a.x + b.x;
  return t >= mod ? t - mod : t;
}
Mint operator-(Mint a, Mint b) {
  int t = a.x - b.x;
  return t < 0 ? t + mod : t;
}
Mint operator*(Mint a, Mint b) { return long long(a.x) * b.x % mod; }
Mint operator/(Mint a, Mint b) {
  return long long(a.x) * Qpow(b.x, mod - 2) % mod;
}
Mint f[MAXN], prs[MAXN];
int s[MAXN], a[MAXN];
Mint sgn(int x) { return x & 1 ? -1 : 1; }
int main() {
  int n = read(), top = 0;
  for (int i = 1; i <= n; ++i) a[i] = read();
  f[0] = prs[0] = 1;
  Mint sum = 0;
  for (int i = 1; i <= n; ++i) {
    while (top && a[s[top]] > a[i]) {
      if (top == 1)
        sum -= prs[s[top] - 1] * (a[s[top]] - a[i]);
      else
        sum -= (prs[s[top] - 1] - prs[s[top - 1] - 1]) * (a[s[top]] - a[i]);
      --top;
    }
    s[++top] = i, sum += f[i - 1] * a[i];
    f[i] = -sum, prs[i] = prs[i - 1] + f[i];
  }
  printf("%d\n", (f[n] * sgn(n)).x);
  return 0;
}

### Prompt

Create a solution in Cpp for 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>
long long read() {
  long long x = 0, f = 1;
  int c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
  return f * x;
}
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
template <typename T>
bool umin(T& a, T t) {
  if (a > t) return a = t, 1;
  return 0;
}
template <typename T>
bool umax(T& a, T t) {
  if (a < t) return a = t, 1;
  return 0;
}
const int MAXN = 525011, mod = 998244353, inv2 = (mod + 1) >> 1;
const int INF = 1e9 + 233;
long long Qpow(long long a, long long p) {
  if (a == 2 && p == mod - 2) return inv2;
  long long res = 1;
  while (p) {
    if (p & 1) res = res * a % mod;
    a = a * a % mod, p >>= 1;
  }
  return res;
}
struct Mint {
  int x;
  Mint() : x(0) {}
  Mint(long long x) : x((0 <= x && x < mod ? x : (x % mod + mod) % mod)) {}
  void operator+=(Mint you) {
    x += you.x;
    if (x >= mod) x -= mod;
  }
  void operator-=(Mint you) {
    x -= you.x;
    if (x < 0) x += mod;
  }
  void operator*=(Mint you) { x = long long(x) * you.x % mod; }
  void operator/=(Mint you) { x = long long(x) * Qpow(you.x, mod - 2) % mod; }
  Mint operator-() { return x ? mod - x : 0; }
  Mint Inv() { return Qpow(x, mod - 2); }
};
Mint operator+(Mint a, Mint b) {
  int t = a.x + b.x;
  return t >= mod ? t - mod : t;
}
Mint operator-(Mint a, Mint b) {
  int t = a.x - b.x;
  return t < 0 ? t + mod : t;
}
Mint operator*(Mint a, Mint b) { return long long(a.x) * b.x % mod; }
Mint operator/(Mint a, Mint b) {
  return long long(a.x) * Qpow(b.x, mod - 2) % mod;
}
Mint f[MAXN], prs[MAXN];
int s[MAXN], a[MAXN];
Mint sgn(int x) { return x & 1 ? -1 : 1; }
int main() {
  int n = read(), top = 0;
  for (int i = 1; i <= n; ++i) a[i] = read();
  f[0] = prs[0] = 1;
  Mint sum = 0;
  for (int i = 1; i <= n; ++i) {
    while (top && a[s[top]] > a[i]) {
      if (top == 1)
        sum -= prs[s[top] - 1] * (a[s[top]] - a[i]);
      else
        sum -= (prs[s[top] - 1] - prs[s[top - 1] - 1]) * (a[s[top]] - a[i]);
      --top;
    }
    s[++top] = i, sum += f[i - 1] * a[i];
    f[i] = -sum, prs[i] = prs[i - 1] + f[i];
  }
  printf("%d\n", (f[n] * sgn(n)).x);
  return 0;
}

```