#include <bits/stdc++.h>
using namespace std;
const long long P = 998244353;
inline long long mod(long long x) {
  long long y = x % P;
  return y < 0 ? y + P : y;
}
struct Node {
  struct Node *left = nullptr, *right = nullptr;
  long long sum = 0, lazy = 0;
  bool toShift = false;
};
void push(Node *node, long long l, long long m, long long r) {
  if (not node->left) node->left = new Node();
  if (not node->right) node->right = new Node();
  if (not node->toShift) return;
  node->left->sum = mod((m - l) * node->lazy);
  node->left->lazy = node->lazy;
  node->left->toShift = true;
  node->right->sum = mod((r - m) * node->lazy);
  node->right->lazy = node->lazy;
  node->right->toShift = true;
  node->toShift = false;
}
void update(Node *node, long long l, long long r, long long l1, long long r1,
            long long v) {
  if (l1 == r1) return;
  if (l == l1 and r == r1) {
    node->sum = mod((r - l) * v);
    node->lazy = v;
    node->toShift = true;
    return;
  }
  long long m = (l + r) >> 1;
  push(node, l, m, r);
  update(node->left, l, m, min(l1, m), min(r1, m), v);
  update(node->right, m, r, max(l1, m), max(r1, m), v);
  node->sum = mod(node->left->sum + node->right->sum);
}
void test() {
  long long n;
  cin >> n;
  vector<long long> a(n);
  for (long long &a1 : a) cin >> a1;
  Node *seg = new Node();
  long long l = 1, r = 1e9 + 1;
  long long m = 1, k = 0;
  update(seg, l, r, 1, a[0] + 1, 1);
  for (long long i = 1; i < n; i++) {
    long long s = mod(m * seg->sum + k * (r - l));
    m = -m;
    k = mod(s - k);
    long long v = mod(-k / m);
    update(seg, l, r, a[i] + 1, r, v);
  }
  cout << mod(m * seg->sum + k * (r - l)) << '\n';
}
signed main() {
  iostream::sync_with_stdio(false);
  long long q = 1;
  while (q--) test();
  assert(cin);
}

### Prompt

In Cpp, your task is to solve 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 long long P = 998244353;
inline long long mod(long long x) {
  long long y = x % P;
  return y < 0 ? y + P : y;
}
struct Node {
  struct Node *left = nullptr, *right = nullptr;
  long long sum = 0, lazy = 0;
  bool toShift = false;
};
void push(Node *node, long long l, long long m, long long r) {
  if (not node->left) node->left = new Node();
  if (not node->right) node->right = new Node();
  if (not node->toShift) return;
  node->left->sum = mod((m - l) * node->lazy);
  node->left->lazy = node->lazy;
  node->left->toShift = true;
  node->right->sum = mod((r - m) * node->lazy);
  node->right->lazy = node->lazy;
  node->right->toShift = true;
  node->toShift = false;
}
void update(Node *node, long long l, long long r, long long l1, long long r1,
            long long v) {
  if (l1 == r1) return;
  if (l == l1 and r == r1) {
    node->sum = mod((r - l) * v);
    node->lazy = v;
    node->toShift = true;
    return;
  }
  long long m = (l + r) >> 1;
  push(node, l, m, r);
  update(node->left, l, m, min(l1, m), min(r1, m), v);
  update(node->right, m, r, max(l1, m), max(r1, m), v);
  node->sum = mod(node->left->sum + node->right->sum);
}
void test() {
  long long n;
  cin >> n;
  vector<long long> a(n);
  for (long long &a1 : a) cin >> a1;
  Node *seg = new Node();
  long long l = 1, r = 1e9 + 1;
  long long m = 1, k = 0;
  update(seg, l, r, 1, a[0] + 1, 1);
  for (long long i = 1; i < n; i++) {
    long long s = mod(m * seg->sum + k * (r - l));
    m = -m;
    k = mod(s - k);
    long long v = mod(-k / m);
    update(seg, l, r, a[i] + 1, r, v);
  }
  cout << mod(m * seg->sum + k * (r - l)) << '\n';
}
signed main() {
  iostream::sync_with_stdio(false);
  long long q = 1;
  while (q--) test();
  assert(cin);
}

```