#include <bits/stdc++.h>
const int P = 998244353;
using namespace std;
template <class T>
using vector2D = vector<vector<T>>;
template <class T>
using vector3D = vector<vector2D<T>>;
template <class T>
using pque = priority_queue<T>;
template <class T>
using heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
bool umax(T &x, T y) {
  return (x < y) ? x = y, true : false;
}
template <class T>
bool umin(T &x, T y) {
  return (x > y) ? x = y, true : false;
}
void prepare() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
const int maxn = 200005;
int top;
long long mul, add;
long long num[maxn];
long long stk[maxn];
long long sum;
long long power(long long a, long long b, long long c = P) {
  long long r = 1;
  for (r %= c, a %= c; b; b >>= 1, a = a * a % c)
    if (b & 1) r = r * a % c;
  return r;
}
int main() {
  prepare();
  int n;
  long long y;
  cin >> n;
  cin >> y;
  top = 1;
  mul = 1;
  add = 0;
  sum = y;
  stk[1] = y;
  num[1] = 1;
  for (int i = 2; i <= n; i++) {
    long long x;
    cin >> x;
    if (x <= y) {
      long long sum0 = sum;
      while (x < stk[top]) {
        long long l = max(x, stk[top - 1]);
        sum = (sum - (num[top] * mul + add) % P * (stk[top] - l) % P + P) % P;
        --top;
      }
      if (x > stk[top]) {
        ++top;
        stk[top] = x;
      }
      add *= -1;
      mul *= -1;
      sum *= -1;
      add = (add + sum0) % P;
      sum = (sum + sum0 * x) % P;
    } else {
      long long sum0 = sum;
      add *= -1;
      mul *= -1;
      sum *= -1;
      add = (add + sum0) % P;
      sum = (sum + sum0 * x) % P;
      stk[++top] = x;
      num[top] = (sum0 - add) * power(mul, P - 2) % P;
    }
    y = x;
  }
  cout << ((sum + P) % P + P) % P << endl;
  return 0;
}

### Prompt

Develop a solution in Cpp 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>
const int P = 998244353;
using namespace std;
template <class T>
using vector2D = vector<vector<T>>;
template <class T>
using vector3D = vector<vector2D<T>>;
template <class T>
using pque = priority_queue<T>;
template <class T>
using heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
bool umax(T &x, T y) {
  return (x < y) ? x = y, true : false;
}
template <class T>
bool umin(T &x, T y) {
  return (x > y) ? x = y, true : false;
}
void prepare() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
const int maxn = 200005;
int top;
long long mul, add;
long long num[maxn];
long long stk[maxn];
long long sum;
long long power(long long a, long long b, long long c = P) {
  long long r = 1;
  for (r %= c, a %= c; b; b >>= 1, a = a * a % c)
    if (b & 1) r = r * a % c;
  return r;
}
int main() {
  prepare();
  int n;
  long long y;
  cin >> n;
  cin >> y;
  top = 1;
  mul = 1;
  add = 0;
  sum = y;
  stk[1] = y;
  num[1] = 1;
  for (int i = 2; i <= n; i++) {
    long long x;
    cin >> x;
    if (x <= y) {
      long long sum0 = sum;
      while (x < stk[top]) {
        long long l = max(x, stk[top - 1]);
        sum = (sum - (num[top] * mul + add) % P * (stk[top] - l) % P + P) % P;
        --top;
      }
      if (x > stk[top]) {
        ++top;
        stk[top] = x;
      }
      add *= -1;
      mul *= -1;
      sum *= -1;
      add = (add + sum0) % P;
      sum = (sum + sum0 * x) % P;
    } else {
      long long sum0 = sum;
      add *= -1;
      mul *= -1;
      sum *= -1;
      add = (add + sum0) % P;
      sum = (sum + sum0 * x) % P;
      stk[++top] = x;
      num[top] = (sum0 - add) * power(mul, P - 2) % P;
    }
    y = x;
  }
  cout << ((sum + P) % P + P) % P << endl;
  return 0;
}

```