#include <bits/stdc++.h>
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
  return f * x;
}
const int MAXN = 265011, mod = 998244353, inv2 = (mod + 1) >> 1;
long long Qpow(long long a, long long p) {
  long long res = 1;
  while (p) {
    if (p & 1) res = res * a % mod;
    a = a * a % mod, p >>= 1;
  }
  return res;
}
void Add(int& a, int t) {
  a += t;
  if (a >= mod) a -= mod;
}
inline int S(int x) { return x < mod ? x : x - mod; }
inline int D(int x) { return x < 0 ? x + mod : x; }
namespace NTT {
long long RT[MAXN], invL[MAXN];
void init() {
  invL[1] = 1;
  for (int i = 1; i < (1 << 18); i <<= 1) {
    long long R = Qpow(3, (mod - 1) / (i << 1));
    RT[i] = 1;
    for (int j = 1; j < i; ++j) RT[i + j] = RT[i + j - 1] * R % mod;
    invL[i << 1] = invL[i] * inv2 % mod;
  }
}
int f[MAXN], g[MAXN], status[MAXN];
void DFT(int* a, int len) {
  for (int i = 0; i < len; ++i)
    if (status[i] > i) std::swap(a[i], a[status[i]]);
  for (int cur = 1; cur < len; cur <<= 1)
    for (int j = 0; j < len; j += cur << 1)
      for (int k = 0; k < cur; ++k) {
        int x = a[j + k], y = RT[cur + k] * a[j + cur + k] % mod;
        a[j + k] = S(x + y), a[j + cur + k] = D(x - y);
      }
}
void IDFT(int* a, int len) {
  std::reverse(a + 1, a + len);
  DFT(a, len);
  for (int i = 0; i < len; ++i) a[i] = a[i] * invL[len] % mod;
}
void Mul(int n) {
  int len = 1;
  while (len < n) len <<= 1;
  for (int i = 0; i < len; ++i)
    status[i] = (status[i >> 1] >> 1) | ((i & 1) ? len >> 1 : 0);
  DFT(f, len), DFT(g, len);
  for (int i = 0; i < len; ++i) f[i] = long long(f[i]) * g[i] % mod, g[i] = 0;
  IDFT(f, len);
}
}  // namespace NTT
struct poly : std::vector<int> {
  poly() { clear(); }
  poly(int x) { resize(x); }
  poly operator+(poly you) {
    poly res = *this;
    if (res.size() < you.size()) res.resize(you.size());
    for (int i = 0; i < you.size(); ++i) Add(res[i], you[i]);
    return res;
  }
  poly operator*(poly you) {
    if (empty() || you.empty()) return poly();
    int n = size() + you.size() - 1;
    poly res(n);
    for (int i = 0; i < size(); ++i) NTT::f[i] = (*this)[i];
    for (int i = 0; i < you.size(); ++i) NTT::g[i] = you[i];
    NTT::Mul(n);
    for (int i = 0; i < n; ++i) res[i] = NTT::f[i], NTT::f[i] = 0;
    return res;
  }
};
struct Matrix {
  poly a[4];
  Matrix() {}
  Matrix(poly* b) { a[0] = b[0], a[1] = b[1], a[2] = b[2], a[3] = b[3]; }
  Matrix operator*(Matrix you) {
    poly tp[4];
    tp[0] = (a[0] * you.a[0] + a[1] * you.a[2]);
    tp[1] = (a[0] * you.a[1] + a[1] * you.a[3]);
    tp[2] = (a[2] * you.a[0] + a[3] * you.a[2]);
    tp[3] = (a[2] * you.a[1] + a[3] * you.a[3]);
    return Matrix(tp);
  }
} mat[MAXN];
int a[MAXN];
long long fac[MAXN];
Matrix merge(int l, int r) {
  if (l == r) return mat[l];
  int mid = (l + r) >> 1;
  return merge(l, mid) * merge(mid + 1, r);
}
int main() {
  NTT::init();
  int n = read();
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
  for (int i = 1; i <= n; ++i) a[i] = read();
  int cur = 0;
  for (int i = 1, j; i <= n; i = j) {
    j = i + 1;
    while (j - i + 1 <= a[i] && a[j] == a[i]) ++j;
    if (j - i < a[i]) {
      puts("0");
      return 0;
    }
    ++cur;
    if (cur == 1) {
      if (a[i] == 1)
        mat[1].a[0].push_back(0), mat[1].a[0].push_back(1);
      else
        mat[1].a[1].push_back(0), mat[1].a[1].push_back(2);
    } else {
      if (a[i] == 1) {
        mat[cur].a[0].push_back(0), mat[cur].a[0].push_back(1);
        mat[cur].a[1].push_back(2);
        mat[cur].a[2] = mat[cur].a[0];
        mat[cur].a[3].push_back(1);
      } else {
        mat[cur].a[1].push_back(2), mat[cur].a[1].push_back(2);
        mat[cur].a[3].push_back(1), mat[cur].a[3].push_back(2);
      }
    }
  }
  if (cur > 1) mat[1] = mat[1] * merge(2, cur);
  poly res = (mat[1].a[0] + mat[1].a[1]);
  res.resize(cur + 1);
  long long ans = 0;
  for (int i = 1; i <= cur; ++i) {
    if ((cur - i) & 1)
      ans = (ans - fac[i] * (res[i])) % mod;
    else
      ans = (ans + fac[i] * (res[i])) % mod;
  }
  printf("%lld\n", (ans + mod) % mod);
  return 0;
}

### Prompt

Please formulate 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>
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
  return f * x;
}
const int MAXN = 265011, mod = 998244353, inv2 = (mod + 1) >> 1;
long long Qpow(long long a, long long p) {
  long long res = 1;
  while (p) {
    if (p & 1) res = res * a % mod;
    a = a * a % mod, p >>= 1;
  }
  return res;
}
void Add(int& a, int t) {
  a += t;
  if (a >= mod) a -= mod;
}
inline int S(int x) { return x < mod ? x : x - mod; }
inline int D(int x) { return x < 0 ? x + mod : x; }
namespace NTT {
long long RT[MAXN], invL[MAXN];
void init() {
  invL[1] = 1;
  for (int i = 1; i < (1 << 18); i <<= 1) {
    long long R = Qpow(3, (mod - 1) / (i << 1));
    RT[i] = 1;
    for (int j = 1; j < i; ++j) RT[i + j] = RT[i + j - 1] * R % mod;
    invL[i << 1] = invL[i] * inv2 % mod;
  }
}
int f[MAXN], g[MAXN], status[MAXN];
void DFT(int* a, int len) {
  for (int i = 0; i < len; ++i)
    if (status[i] > i) std::swap(a[i], a[status[i]]);
  for (int cur = 1; cur < len; cur <<= 1)
    for (int j = 0; j < len; j += cur << 1)
      for (int k = 0; k < cur; ++k) {
        int x = a[j + k], y = RT[cur + k] * a[j + cur + k] % mod;
        a[j + k] = S(x + y), a[j + cur + k] = D(x - y);
      }
}
void IDFT(int* a, int len) {
  std::reverse(a + 1, a + len);
  DFT(a, len);
  for (int i = 0; i < len; ++i) a[i] = a[i] * invL[len] % mod;
}
void Mul(int n) {
  int len = 1;
  while (len < n) len <<= 1;
  for (int i = 0; i < len; ++i)
    status[i] = (status[i >> 1] >> 1) | ((i & 1) ? len >> 1 : 0);
  DFT(f, len), DFT(g, len);
  for (int i = 0; i < len; ++i) f[i] = long long(f[i]) * g[i] % mod, g[i] = 0;
  IDFT(f, len);
}
}  // namespace NTT
struct poly : std::vector<int> {
  poly() { clear(); }
  poly(int x) { resize(x); }
  poly operator+(poly you) {
    poly res = *this;
    if (res.size() < you.size()) res.resize(you.size());
    for (int i = 0; i < you.size(); ++i) Add(res[i], you[i]);
    return res;
  }
  poly operator*(poly you) {
    if (empty() || you.empty()) return poly();
    int n = size() + you.size() - 1;
    poly res(n);
    for (int i = 0; i < size(); ++i) NTT::f[i] = (*this)[i];
    for (int i = 0; i < you.size(); ++i) NTT::g[i] = you[i];
    NTT::Mul(n);
    for (int i = 0; i < n; ++i) res[i] = NTT::f[i], NTT::f[i] = 0;
    return res;
  }
};
struct Matrix {
  poly a[4];
  Matrix() {}
  Matrix(poly* b) { a[0] = b[0], a[1] = b[1], a[2] = b[2], a[3] = b[3]; }
  Matrix operator*(Matrix you) {
    poly tp[4];
    tp[0] = (a[0] * you.a[0] + a[1] * you.a[2]);
    tp[1] = (a[0] * you.a[1] + a[1] * you.a[3]);
    tp[2] = (a[2] * you.a[0] + a[3] * you.a[2]);
    tp[3] = (a[2] * you.a[1] + a[3] * you.a[3]);
    return Matrix(tp);
  }
} mat[MAXN];
int a[MAXN];
long long fac[MAXN];
Matrix merge(int l, int r) {
  if (l == r) return mat[l];
  int mid = (l + r) >> 1;
  return merge(l, mid) * merge(mid + 1, r);
}
int main() {
  NTT::init();
  int n = read();
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
  for (int i = 1; i <= n; ++i) a[i] = read();
  int cur = 0;
  for (int i = 1, j; i <= n; i = j) {
    j = i + 1;
    while (j - i + 1 <= a[i] && a[j] == a[i]) ++j;
    if (j - i < a[i]) {
      puts("0");
      return 0;
    }
    ++cur;
    if (cur == 1) {
      if (a[i] == 1)
        mat[1].a[0].push_back(0), mat[1].a[0].push_back(1);
      else
        mat[1].a[1].push_back(0), mat[1].a[1].push_back(2);
    } else {
      if (a[i] == 1) {
        mat[cur].a[0].push_back(0), mat[cur].a[0].push_back(1);
        mat[cur].a[1].push_back(2);
        mat[cur].a[2] = mat[cur].a[0];
        mat[cur].a[3].push_back(1);
      } else {
        mat[cur].a[1].push_back(2), mat[cur].a[1].push_back(2);
        mat[cur].a[3].push_back(1), mat[cur].a[3].push_back(2);
      }
    }
  }
  if (cur > 1) mat[1] = mat[1] * merge(2, cur);
  poly res = (mat[1].a[0] + mat[1].a[1]);
  res.resize(cur + 1);
  long long ans = 0;
  for (int i = 1; i <= cur; ++i) {
    if ((cur - i) & 1)
      ans = (ans - fac[i] * (res[i])) % mod;
    else
      ans = (ans + fac[i] * (res[i])) % mod;
  }
  printf("%lld\n", (ans + mod) % mod);
  return 0;
}

```