#include <bits/stdc++.h>
using namespace std;
const int md = 998244353;
struct lzT {
  long long add;
  int mul;
};
struct Node {
  long long res = 0;
  lzT lz = {0, 1};
  int hi, lo;
  Node *L, *R;
  Node(int _lo, int _hi) : lo(_lo), hi(_hi) { L = R = nullptr; }
  void extend() {
    if (L or R or lo == hi) return;
    int mid = (lo + hi) / 2;
    L = new Node(lo, mid);
    R = new Node(mid + 1, hi);
  }
  lzT combLz(lzT a, lzT b) {
    return {(a.mul * b.add + a.add + md) % md, a.mul * b.mul};
  }
  long long applyLz() {
    return (res * lz.mul + lz.add * (hi - lo + 1) + md) % md;
  }
  void push() {
    res = applyLz();
    if (lo != hi) {
      L->lz = combLz(lz, L->lz);
      R->lz = combLz(lz, R->lz);
    }
    lz = {0, 1};
  }
  void upd(int ql, int qr, lzT val) {
    if (lo > qr or hi < ql) return;
    if (lo >= ql and hi <= qr) {
      lz = combLz(val, lz);
      return;
    }
    extend();
    push();
    L->upd(ql, qr, val);
    R->upd(ql, qr, val);
    res = (L->applyLz() + R->applyLz()) % md;
  }
  long long qry(int ql, int qr) {
    if (lo > qr or hi < ql) return {};
    if (lo >= ql and hi <= qr) return applyLz();
    extend();
    push();
    return (L->qry(ql, qr) + R->qry(ql, qr)) % md;
  }
};
Node* seg = new Node(0, 1e9);
int main() {
  int n;
  cin >> n;
  for (int i = 0, num; i < n; i++) {
    cin >> num;
    if (!i)
      seg->upd(1, num, {1, 1});
    else {
      long long sm = seg->qry(1, 1e9);
      seg->upd(1, num, {sm, -1});
      seg->upd(num + 1, 1e9, {0, 0});
    }
  }
  cout << seg->qry(1, 1e9) << endl;
}

### Prompt

Please create a solution in cpp 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 md = 998244353;
struct lzT {
  long long add;
  int mul;
};
struct Node {
  long long res = 0;
  lzT lz = {0, 1};
  int hi, lo;
  Node *L, *R;
  Node(int _lo, int _hi) : lo(_lo), hi(_hi) { L = R = nullptr; }
  void extend() {
    if (L or R or lo == hi) return;
    int mid = (lo + hi) / 2;
    L = new Node(lo, mid);
    R = new Node(mid + 1, hi);
  }
  lzT combLz(lzT a, lzT b) {
    return {(a.mul * b.add + a.add + md) % md, a.mul * b.mul};
  }
  long long applyLz() {
    return (res * lz.mul + lz.add * (hi - lo + 1) + md) % md;
  }
  void push() {
    res = applyLz();
    if (lo != hi) {
      L->lz = combLz(lz, L->lz);
      R->lz = combLz(lz, R->lz);
    }
    lz = {0, 1};
  }
  void upd(int ql, int qr, lzT val) {
    if (lo > qr or hi < ql) return;
    if (lo >= ql and hi <= qr) {
      lz = combLz(val, lz);
      return;
    }
    extend();
    push();
    L->upd(ql, qr, val);
    R->upd(ql, qr, val);
    res = (L->applyLz() + R->applyLz()) % md;
  }
  long long qry(int ql, int qr) {
    if (lo > qr or hi < ql) return {};
    if (lo >= ql and hi <= qr) return applyLz();
    extend();
    push();
    return (L->qry(ql, qr) + R->qry(ql, qr)) % md;
  }
};
Node* seg = new Node(0, 1e9);
int main() {
  int n;
  cin >> n;
  for (int i = 0, num; i < n; i++) {
    cin >> num;
    if (!i)
      seg->upd(1, num, {1, 1});
    else {
      long long sm = seg->qry(1, 1e9);
      seg->upd(1, num, {sm, -1});
      seg->upd(num + 1, 1e9, {0, 0});
    }
  }
  cout << seg->qry(1, 1e9) << endl;
}

```