description: 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].
solution: #include <bits/stdc++.h>
  using namespace std;
  const int MOD = 998244353;
  inline int add(int a, int b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
  inline void inc(int &a, int b) { a = add(a, b); }
  inline int sub(int a, int b) { return (a - b < 0) ? a - b + MOD : a - b; }
  inline void dec(int &a, int b) { a = sub(a, b); }
  inline int mul(int a, int b) { return 1ll * a * b % MOD; }
  inline void grow(int &a, int b) { a = mul(a, b); }
  struct node {
    int sum, tl, tr, a, b;
    node *l, *r;
    node(int _sum, int _tl, int _tr, int _a = 1, int _b = 0) {
      sum = _sum, tl = _tl, tr = _tr, a = _a, b = _b;
      l = nullptr;
      r = nullptr;
    }
    void push() {
      if (tl != tr) {
        if (!l) {
          int tm = (tl + tr) >> 1;
          l = new node(sum, tl, tm);
          r = new node(sum, tm + 1, tr);
        }
        grow(l->a, a);
        l->b = add(mul(a, l->b), b);
        grow(r->a, a);
        r->b = add(mul(a, r->b), b);
      }
      sum = add(mul(a, sum), mul(b, (tr - tl + 1) % MOD));
      a = 1, b = 0;
    }
    void upd(int l, int r, int na, int nb) {
      push();
      if (tr < l || tl > r) return;
      if (l <= tl && tr <= r) {
        grow(a, na);
        b = add(mul(na, b), nb);
        push();
        return;
      }
      this->l->upd(l, r, na, nb);
      this->r->upd(l, r, na, nb);
      sum = add(this->l->sum, this->r->sum);
    }
  };
  node *root = new node(0, 1, 1000000000);
  int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      int b;
      cin >> b;
      root->upd(1, b, MOD - 1, i ? root->sum : 1);
      root->upd(b + 1, 1000000000, 0, 0);
    }
    cout << root->sum << '\n';
  }
  