#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, _G = 3, N = (1 << 19), inv2 = (mod + 1) / 2;
int qpow(int x, int y = mod - 2) {
  int res = 1;
  for (; y; x = (long long)x * x % mod, y >>= 1)
    if (y & 1) res = (long long)res * x % mod;
  return res;
}
int n, fn, m, fac[N], ifac[N], inv[N];
void init(int x) {
  fac[0] = ifac[0] = inv[1] = 1;
  for (int i = (2); i <= (x); ++i)
    inv[i] = (long long)inv[mod % i] * (mod - mod / i) % mod;
  for (int i = (1); i <= (x); ++i)
    fac[i] = (long long)fac[i - 1] * i % mod,
    ifac[i] = (long long)ifac[i - 1] * inv[i] % mod;
}
int rt[N], Lim;
void Pinit(int x) {
  for (Lim = 1; Lim <= x; Lim <<= 1)
    ;
  int sG = qpow(_G, (mod - 1) / Lim);
  rt[0] = 1;
  for (int i = (1); i <= (Lim); ++i) rt[i] = (long long)rt[i - 1] * sG % mod;
}
int C(int x, int y) {
  return y < 0 || x < y ? 0
                        : (long long)fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int rev[N];
void initrev(int n) {
  for (int i = (0); i <= (n - 1); ++i)
    rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) * (n >> 1)));
}
struct poly {
  vector<int> a;
  int size() { return ((int)a.size()); }
  int &operator[](int x) { return a[x]; }
  int v(int x) { return x < 0 || x >= ((int)a.size()) ? 0 : a[x]; }
  void clear() { vector<int>().swap(a); }
  void rs(int x = 0) { a.resize(x); }
  poly(int n = 0) { rs(n); }
  poly(vector<int> o) { a = o; }
  poly(const poly &o) { a = o.a; }
  poly Rs(int x = 0) {
    vector<int> res = a;
    res.resize(x);
    return res;
  }
  inline void ntt(int op, int t = true) {
    int n = ((int)a.size());
    if (t) initrev(n);
    for (int i = (0); i <= (n - 1); ++i)
      if (rev[i] < i) swap(a[rev[i]], a[i]);
    for (int i = 2; i <= n; i <<= 1)
      for (int j = 0, l = (i >> 1), ch = Lim / i; j < n; j += i)
        for (int k = j, now = 0; k < j + l; k++) {
          int pa = a[k], pb = (long long)a[k + l] *
                              (op == 1 ? rt[now] : rt[Lim - now]) % mod;
          a[k] = (pa + pb >= mod ? pa + pb - mod : pa + pb),
          a[k + l] = (pa < pb ? pa - pb + mod : pa - pb), now += ch;
        }
    if (op != 1)
      for (int i = 0, iv = qpow(n); i < n; i++)
        a[i] = (long long)a[i] * iv % mod;
  }
  poly Shift(int x) {
    poly zm(max(((int)a.size()) + x, 0));
    for (int i = (max(0, -x)); i <= (((int)a.size()) - 1); ++i)
      zm[i + x] = a[i];
    return zm;
  }
  friend poly operator*(poly aa, poly bb) {
    if (!((int)aa.size()) || !((int)bb.size())) return {};
    int lim, all = ((int)aa.size()) + ((int)bb.size()) - 1;
    for (lim = 1; lim < all; lim <<= 1)
      ;
    initrev(lim), aa.rs(lim), bb.rs(lim), aa.ntt(1, false), bb.ntt(1, false);
    for (int i = (0); i <= (lim - 1); ++i)
      aa[i] = (long long)aa[i] * bb[i] % mod;
    aa.ntt(-1, false), aa.a.resize(all);
    return aa;
  }
  friend poly operator*(poly aa, int bb) {
    poly res(((int)aa.size()));
    for (int i = (0); i <= (((int)aa.size()) - 1); ++i)
      res[i] = (long long)aa[i] * bb % mod;
    return res;
  }
  friend poly operator+(poly aa, poly bb) {
    vector<int> res(max(((int)aa.size()), ((int)bb.size())));
    for (int i = (0); i <= (((int)res.size()) - 1); ++i)
      res[i] = (aa.v(i) + bb.v(i) >= mod ? aa.v(i) + bb.v(i) - mod
                                         : aa.v(i) + bb.v(i));
    return poly(res);
  }
  friend poly operator-(poly aa, poly bb) {
    vector<int> res(max(((int)aa.size()), ((int)bb.size())));
    for (int i = (0); i <= (((int)res.size()) - 1); ++i)
      res[i] =
          (aa.v(i) < bb.v(i) ? aa.v(i) - bb.v(i) + mod : aa.v(i) - bb.v(i));
    return poly(res);
  }
  poly &operator+=(poly o) {
    rs(max(((int)a.size()), ((int)o.size())));
    for (int i = (0); i <= (((int)a.size()) - 1); ++i) (a[i] += o.v(i)) %= mod;
    return (*this);
  }
  poly &operator-=(poly o) {
    rs(max(((int)a.size()), ((int)o.size())));
    for (int i = (0); i <= (((int)a.size()) - 1); ++i)
      (a[i] += mod - o.v(i)) %= mod;
    return (*this);
  }
  poly &operator*=(poly o) { return (*this) = (*this) * o; }
  poly Inv() {
    poly res, f, g;
    res.rs(1), res[0] = qpow(a[0]);
    for (int m = 1, pn; m < ((int)a.size()); m <<= 1) {
      pn = m << 1, f = res, g.rs(pn), f.rs(pn), initrev(pn);
      for (int i = 0; i < pn; i++) g[i] = (*this).v(i);
      f.ntt(1, false), g.ntt(1, false);
      for (int i = 0; i < pn; i++) g[i] = (long long)f[i] * g[i] % mod;
      g.ntt(-1, false);
      for (int i = 0; i < m; i++) g[i] = 0;
      g.ntt(1, false);
      for (int i = 0; i < pn; i++) g[i] = (long long)f[i] * g[i] % mod;
      g.ntt(-1, false), res.rs(pn);
      for (int i = m; i < min(pn, ((int)a.size())); i++)
        res[i] = (mod - g[i]) % mod;
    }
    return res;
  }
  poly Integ() {
    if (!((int)a.size())) return poly();
    poly res(((int)a.size()) + 1);
    for (int i = (1); i <= (((int)a.size())); ++i)
      res[i] = (long long)a[i - 1] * inv[i] % mod;
    return res;
  }
  poly Deriv() {
    if (!((int)a.size())) return poly();
    poly res(((int)a.size()) - 1);
    for (int i = (1); i <= (((int)a.size()) - 1); ++i)
      res[i - 1] = (long long)a[i] * i % mod;
    return res;
  }
  poly Ln() {
    poly g = ((*this).Inv() * (*this).Deriv()).Integ();
    return g.rs(((int)a.size())), g;
  }
  poly Exp() {
    poly res(1), f;
    res[0] = 1;
    for (int m = 1, pn; m < ((int)a.size()); m <<= 1) {
      pn = min(m << 1, ((int)a.size())), f.rs(pn), res.rs(pn);
      for (int i = 0; i < pn; i++) f[i] = (*this).v(i);
      f -= res.Ln(), (f[0] += 1) %= mod, res *= f, res.rs(pn);
    }
    return res.rs(((int)a.size())), res;
  }
  poly pow(int x) {
    poly res = (*this).Ln();
    for (int i = (0); i <= (((int)res.size()) - 1); ++i)
      res[i] = (long long)res[i] * x % mod;
    res = res.Exp();
    return res;
  }
  poly sqrt(int rt = 1) {
    poly res(1), f;
    res[0] = rt;
    for (int m = 1, pn; m < ((int)a.size()); m <<= 1) {
      pn = min(m << 1, ((int)a.size())), f.rs(pn);
      for (int i = 0; i < pn; i++) f[i] = (*this).v(i);
      f += res * res, f.rs(pn), res.rs(pn), res = f * res.Inv(), res.rs(pn);
      for (int i = 0; i < pn; i++) res[i] = (long long)res[i] * inv2 % mod;
    }
    return res;
  }
  void Rev() { reverse(a.begin(), a.end()); }
};
int W[N], f[N];
poly s[N][2][2];
void divide(int x, int l, int r) {
  if (l == r) {
    for (int i = (0); i <= (1); ++i)
      for (int j = (0); j <= (1); ++j) s[x][i][j] = vector<int>{0, 1};
    if (f[l] == 1) s[x][0][0] = vector<int>{0, inv2};
    return;
  }
  int mid = (l + r) >> 1;
  divide(x * 2, l, mid);
  divide(x * 2 + 1, mid + 1, r);
  for (int a = (0); a <= (1); ++a)
    for (int b = (0); b <= (1); ++b)
      s[x][a][b] += (s[x * 2][a][1] * s[x * 2 + 1][1][b]).Shift(-1);
  for (int a = (0); a <= (1); ++a)
    for (int b = (0); b <= (1); ++b)
      s[x][a][b] += s[x * 2][a][0] * s[x * 2 + 1][0][b];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n, init(n * 4), Pinit(n * 4);
  for (int i = (1); i <= (n); ++i) cin >> W[i];
  int cnt = 0;
  for (int i = (1); i <= (n); ++i) {
    ++cnt;
    if (W[i] != W[i + 1]) {
      if (cnt % W[i]) return cout << 0 << "\n", 0;
      for (int t = (1); t <= (cnt / W[i]); ++t) f[++m] = W[i];
      cnt = 0;
    }
  }
  divide(1, 1, m);
  int res = 0;
  for (int i = (0); i <= (((int)s[1][0][0].size()) - 1); ++i)
    (res += (long long)s[1][0][0][i] * qpow(2, i) % mod * fac[i] % mod *
            qpow(mod - 1, m - i) % mod) %= mod;
  cout << res << "\n";
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

For a permutation p of numbers 1 through n, we define a stair array a as follows: a_i is length of the longest segment of permutation which contains position i and is made of consecutive values in sorted order: [x, x+1, …, y-1, y] or [y, y-1, …, x+1, x] for some x ≤ y. For example, for permutation p = [4, 1, 2, 3, 7, 6, 5] we have a = [1, 3, 3, 3, 3, 3, 3]. 

You are given the stair array a. Your task is to calculate the number of permutations which have stair array equal to a. Since the number can be big, compute it modulo 998 244 353. Note that this number can be equal to zero.

Input

The first line of input contains integer n (1 ≤ n ≤ 10^5) — the length of a stair array a.

The second line of input contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n).

Output

Print the number of permutations which have stair array equal to a. Since the number can be big, compute it modulo 998 244 353.

Examples

Input


6
3 3 3 1 1 1


Output


6


Input


7
4 4 4 4 3 3 3


Output


6


Input


1
1


Output


1


Input


8
2 2 2 2 2 2 1 1


Output


370


Input


4
3 2 3 1


Output


0

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, _G = 3, N = (1 << 19), inv2 = (mod + 1) / 2;
int qpow(int x, int y = mod - 2) {
  int res = 1;
  for (; y; x = (long long)x * x % mod, y >>= 1)
    if (y & 1) res = (long long)res * x % mod;
  return res;
}
int n, fn, m, fac[N], ifac[N], inv[N];
void init(int x) {
  fac[0] = ifac[0] = inv[1] = 1;
  for (int i = (2); i <= (x); ++i)
    inv[i] = (long long)inv[mod % i] * (mod - mod / i) % mod;
  for (int i = (1); i <= (x); ++i)
    fac[i] = (long long)fac[i - 1] * i % mod,
    ifac[i] = (long long)ifac[i - 1] * inv[i] % mod;
}
int rt[N], Lim;
void Pinit(int x) {
  for (Lim = 1; Lim <= x; Lim <<= 1)
    ;
  int sG = qpow(_G, (mod - 1) / Lim);
  rt[0] = 1;
  for (int i = (1); i <= (Lim); ++i) rt[i] = (long long)rt[i - 1] * sG % mod;
}
int C(int x, int y) {
  return y < 0 || x < y ? 0
                        : (long long)fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int rev[N];
void initrev(int n) {
  for (int i = (0); i <= (n - 1); ++i)
    rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) * (n >> 1)));
}
struct poly {
  vector<int> a;
  int size() { return ((int)a.size()); }
  int &operator[](int x) { return a[x]; }
  int v(int x) { return x < 0 || x >= ((int)a.size()) ? 0 : a[x]; }
  void clear() { vector<int>().swap(a); }
  void rs(int x = 0) { a.resize(x); }
  poly(int n = 0) { rs(n); }
  poly(vector<int> o) { a = o; }
  poly(const poly &o) { a = o.a; }
  poly Rs(int x = 0) {
    vector<int> res = a;
    res.resize(x);
    return res;
  }
  inline void ntt(int op, int t = true) {
    int n = ((int)a.size());
    if (t) initrev(n);
    for (int i = (0); i <= (n - 1); ++i)
      if (rev[i] < i) swap(a[rev[i]], a[i]);
    for (int i = 2; i <= n; i <<= 1)
      for (int j = 0, l = (i >> 1), ch = Lim / i; j < n; j += i)
        for (int k = j, now = 0; k < j + l; k++) {
          int pa = a[k], pb = (long long)a[k + l] *
                              (op == 1 ? rt[now] : rt[Lim - now]) % mod;
          a[k] = (pa + pb >= mod ? pa + pb - mod : pa + pb),
          a[k + l] = (pa < pb ? pa - pb + mod : pa - pb), now += ch;
        }
    if (op != 1)
      for (int i = 0, iv = qpow(n); i < n; i++)
        a[i] = (long long)a[i] * iv % mod;
  }
  poly Shift(int x) {
    poly zm(max(((int)a.size()) + x, 0));
    for (int i = (max(0, -x)); i <= (((int)a.size()) - 1); ++i)
      zm[i + x] = a[i];
    return zm;
  }
  friend poly operator*(poly aa, poly bb) {
    if (!((int)aa.size()) || !((int)bb.size())) return {};
    int lim, all = ((int)aa.size()) + ((int)bb.size()) - 1;
    for (lim = 1; lim < all; lim <<= 1)
      ;
    initrev(lim), aa.rs(lim), bb.rs(lim), aa.ntt(1, false), bb.ntt(1, false);
    for (int i = (0); i <= (lim - 1); ++i)
      aa[i] = (long long)aa[i] * bb[i] % mod;
    aa.ntt(-1, false), aa.a.resize(all);
    return aa;
  }
  friend poly operator*(poly aa, int bb) {
    poly res(((int)aa.size()));
    for (int i = (0); i <= (((int)aa.size()) - 1); ++i)
      res[i] = (long long)aa[i] * bb % mod;
    return res;
  }
  friend poly operator+(poly aa, poly bb) {
    vector<int> res(max(((int)aa.size()), ((int)bb.size())));
    for (int i = (0); i <= (((int)res.size()) - 1); ++i)
      res[i] = (aa.v(i) + bb.v(i) >= mod ? aa.v(i) + bb.v(i) - mod
                                         : aa.v(i) + bb.v(i));
    return poly(res);
  }
  friend poly operator-(poly aa, poly bb) {
    vector<int> res(max(((int)aa.size()), ((int)bb.size())));
    for (int i = (0); i <= (((int)res.size()) - 1); ++i)
      res[i] =
          (aa.v(i) < bb.v(i) ? aa.v(i) - bb.v(i) + mod : aa.v(i) - bb.v(i));
    return poly(res);
  }
  poly &operator+=(poly o) {
    rs(max(((int)a.size()), ((int)o.size())));
    for (int i = (0); i <= (((int)a.size()) - 1); ++i) (a[i] += o.v(i)) %= mod;
    return (*this);
  }
  poly &operator-=(poly o) {
    rs(max(((int)a.size()), ((int)o.size())));
    for (int i = (0); i <= (((int)a.size()) - 1); ++i)
      (a[i] += mod - o.v(i)) %= mod;
    return (*this);
  }
  poly &operator*=(poly o) { return (*this) = (*this) * o; }
  poly Inv() {
    poly res, f, g;
    res.rs(1), res[0] = qpow(a[0]);
    for (int m = 1, pn; m < ((int)a.size()); m <<= 1) {
      pn = m << 1, f = res, g.rs(pn), f.rs(pn), initrev(pn);
      for (int i = 0; i < pn; i++) g[i] = (*this).v(i);
      f.ntt(1, false), g.ntt(1, false);
      for (int i = 0; i < pn; i++) g[i] = (long long)f[i] * g[i] % mod;
      g.ntt(-1, false);
      for (int i = 0; i < m; i++) g[i] = 0;
      g.ntt(1, false);
      for (int i = 0; i < pn; i++) g[i] = (long long)f[i] * g[i] % mod;
      g.ntt(-1, false), res.rs(pn);
      for (int i = m; i < min(pn, ((int)a.size())); i++)
        res[i] = (mod - g[i]) % mod;
    }
    return res;
  }
  poly Integ() {
    if (!((int)a.size())) return poly();
    poly res(((int)a.size()) + 1);
    for (int i = (1); i <= (((int)a.size())); ++i)
      res[i] = (long long)a[i - 1] * inv[i] % mod;
    return res;
  }
  poly Deriv() {
    if (!((int)a.size())) return poly();
    poly res(((int)a.size()) - 1);
    for (int i = (1); i <= (((int)a.size()) - 1); ++i)
      res[i - 1] = (long long)a[i] * i % mod;
    return res;
  }
  poly Ln() {
    poly g = ((*this).Inv() * (*this).Deriv()).Integ();
    return g.rs(((int)a.size())), g;
  }
  poly Exp() {
    poly res(1), f;
    res[0] = 1;
    for (int m = 1, pn; m < ((int)a.size()); m <<= 1) {
      pn = min(m << 1, ((int)a.size())), f.rs(pn), res.rs(pn);
      for (int i = 0; i < pn; i++) f[i] = (*this).v(i);
      f -= res.Ln(), (f[0] += 1) %= mod, res *= f, res.rs(pn);
    }
    return res.rs(((int)a.size())), res;
  }
  poly pow(int x) {
    poly res = (*this).Ln();
    for (int i = (0); i <= (((int)res.size()) - 1); ++i)
      res[i] = (long long)res[i] * x % mod;
    res = res.Exp();
    return res;
  }
  poly sqrt(int rt = 1) {
    poly res(1), f;
    res[0] = rt;
    for (int m = 1, pn; m < ((int)a.size()); m <<= 1) {
      pn = min(m << 1, ((int)a.size())), f.rs(pn);
      for (int i = 0; i < pn; i++) f[i] = (*this).v(i);
      f += res * res, f.rs(pn), res.rs(pn), res = f * res.Inv(), res.rs(pn);
      for (int i = 0; i < pn; i++) res[i] = (long long)res[i] * inv2 % mod;
    }
    return res;
  }
  void Rev() { reverse(a.begin(), a.end()); }
};
int W[N], f[N];
poly s[N][2][2];
void divide(int x, int l, int r) {
  if (l == r) {
    for (int i = (0); i <= (1); ++i)
      for (int j = (0); j <= (1); ++j) s[x][i][j] = vector<int>{0, 1};
    if (f[l] == 1) s[x][0][0] = vector<int>{0, inv2};
    return;
  }
  int mid = (l + r) >> 1;
  divide(x * 2, l, mid);
  divide(x * 2 + 1, mid + 1, r);
  for (int a = (0); a <= (1); ++a)
    for (int b = (0); b <= (1); ++b)
      s[x][a][b] += (s[x * 2][a][1] * s[x * 2 + 1][1][b]).Shift(-1);
  for (int a = (0); a <= (1); ++a)
    for (int b = (0); b <= (1); ++b)
      s[x][a][b] += s[x * 2][a][0] * s[x * 2 + 1][0][b];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n, init(n * 4), Pinit(n * 4);
  for (int i = (1); i <= (n); ++i) cin >> W[i];
  int cnt = 0;
  for (int i = (1); i <= (n); ++i) {
    ++cnt;
    if (W[i] != W[i + 1]) {
      if (cnt % W[i]) return cout << 0 << "\n", 0;
      for (int t = (1); t <= (cnt / W[i]); ++t) f[++m] = W[i];
      cnt = 0;
    }
  }
  divide(1, 1, m);
  int res = 0;
  for (int i = (0); i <= (((int)s[1][0][0].size()) - 1); ++i)
    (res += (long long)s[1][0][0][i] * qpow(2, i) % mod * fac[i] % mod *
            qpow(mod - 1, m - i) % mod) %= mod;
  cout << res << "\n";
  return 0;
}

```