#include <bits/stdc++.h>
template <typename T>
void read(T &);
template <typename T>
void write(const T &);
const int iinf = 2147483647;
const long long llinf = 9223372036854775807ll;
const int N = 270000;
const int Mod = 998244353, sgn[] = {1, Mod - 1};
int pow(int a, int b, int ans = 1);
namespace Pol {
int add(int a, int b) { return (a += b) >= Mod ? a -= Mod : a; }
int sub(int a, int b) { return (a -= b) < 0 ? a += Mod : a; }
void inc(int &a, int b) { (a += b) >= Mod ? a -= Mod : a; }
void dec(int &a, int b) { (a -= b) < 0 ? a += Mod : a; }
int &reduce(int &x) { return x += x >> 31 & Mod; }
void init_Poly(int n = N);
void DIT(int *A, int lim);
void DIF(int *A, int lim);
std::vector<int> &operator+=(std::vector<int> &a, const std::vector<int> &b);
std::vector<int> mult(const std::vector<int> &A, int n,
                      const std::vector<int> &B, int m);
std::vector<int> operator*(const std::vector<int> &a,
                           const std::vector<int> &b);
unsigned long long tmp[N];
int gw[N];
}  // namespace Pol
class Matrix {
 public:
  std::vector<int> val[2][2];
  friend Matrix operator*(const Matrix &a, const Matrix &b);
};
Matrix work(int l, int r);
Matrix a[N];
int fac[N];
int seg[N], m;
int tmp[N], n;
int main() {
  Pol::init_Poly();
  read(n);
  for (int i = 1; i <= n; ++i) read(tmp[i]);
  for (int i = 1; i <= n;) {
    int now = tmp[i];
    for (int j = i; j <= i + now - 1; ++j) {
      if (tmp[j] != now) {
        puts("0");
        return 0;
      }
    }
    seg[++m] = now;
    i += now;
  }
  fac[0] = 1;
  for (int i = 1; i <= m; ++i) {
    fac[i] = 1ll * fac[i - 1] * i % Mod;
    a[i].val[1][0] = {1};
    a[i].val[0][1] = {0, 2};
    a[i].val[1][1] = {0, 1};
    if (seg[i] == 1) {
      a[i].val[0][0] = {1};
    } else {
      a[i].val[0][0] = {2};
    }
  }
  Matrix ans = work(1, m);
  int res = 0;
  for (size_t i = 0; i < ans.val[0][0].size(); ++i) {
    res = (res + 1ll * fac[m - i] * ans.val[0][0][i] % Mod * sgn[i & 1]) % Mod;
  }
  write(res), putchar('\n');
  return 0;
}
Matrix work(int l, int r) {
  if (l == r) return a[l];
  int m = (l + r) >> 1;
  return work(l, m) * work(m + 1, r);
}
Matrix operator*(const Matrix &a, const Matrix &b) {
  Matrix ans;
  using namespace Pol;
  for (int i = 0; i < 2; ++i) {
    for (int k = 0; k < 2; ++k) {
      for (int j = 0; j < 2; ++j) {
        ans.val[i][j] += a.val[i][k] * b.val[k][j];
      }
    }
  }
  return ans;
}
namespace Pol {
void DIT(int *A, int lim) {
  for (int i = 0; i < lim; ++i) tmp[i] = A[i];
  for (int l = 1; l < lim; l <<= 1) {
    unsigned long long *k = tmp;
    for (int *g = gw; k < tmp + lim; k += (l << 1), ++g) {
      for (unsigned long long *x = k; x < k + l; ++x) {
        int o = x[l] % Mod;
        x[l] = 1ll * (*x + Mod - o) * *g % Mod, *x += o;
      }
    }
  }
  int iv = pow(lim, Mod - 2);
  for (int i = 0; i < lim; ++i) A[i] = 1ll * tmp[i] % Mod * iv % Mod;
  std::reverse(A + 1, A + lim);
}
void DIF(int *A, int lim) {
  for (int i = 0; i < lim; ++i) tmp[i] = A[i];
  for (int l = lim / 2; l >= 1; l >>= 1) {
    unsigned long long *k = tmp;
    for (int *g = gw; k < tmp + lim; k += (l << 1), ++g) {
      for (unsigned long long *x = k; x < k + l; ++x) {
        int o = 1ll * x[l] * *g % Mod;
        x[l] = *x + Mod - o, *x += o;
      }
    }
  }
  for (int i = 0; i < lim; ++i) A[i] = tmp[i] % Mod;
}
std::vector<int> &operator+=(std::vector<int> &a, const std::vector<int> &b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (size_t i = 0; i < a.size() && i < b.size(); ++i) inc(a[i], b[i]);
  return a;
}
std::vector<int> mult(const std::vector<int> &A, int n,
                      const std::vector<int> &B, int m) {
  int lim = 1;
  while (lim < (n + m - 1)) lim <<= 1;
  static int tA[N], tB[N];
  std::copy_n(A.begin(), n, tA), std::fill(tA + n, tA + lim, 0);
  std::copy_n(B.begin(), m, tB), std::fill(tB + m, tB + lim, 0);
  DIF(tA, lim), DIF(tB, lim);
  for (int i = 0; i < lim; ++i) tA[i] = 1ll * tA[i] * tB[i] % Mod;
  DIT(tA, lim);
  std::vector<int> ans(n + m - 1);
  std::copy_n(tA, n + m - 1, ans.begin());
  return ans;
}
std::vector<int> operator*(const std::vector<int> &a,
                           const std::vector<int> &b) {
  return mult(a, a.size(), b, b.size());
}
void init_Poly(int n) {
  int t = 1;
  while ((1 << t) < n) ++t;
  t = std::min(t - 1, 21);
  gw[0] = 1, gw[1 << t] = pow(pow(3, 119), 1 << (21 - t));
  for (int i = t; i; --i)
    gw[1 << (i - 1)] = 1ll * gw[1 << i] * gw[1 << i] % Mod;
  for (int i = 1; i < (1 << t); ++i)
    gw[i] = 1ll * gw[i & (i - 1)] * gw[i & -i] % Mod;
}
}  // namespace Pol
int pow(int a, int b, int ans) {
  while (b) {
    if (b & 1) ans = 1ll * ans * a % Mod;
    a = 1ll * a * a % Mod;
    b >>= 1;
  }
  return ans;
}
template <typename T>
void read(T &Re) {
  T k = 0;
  char ch = getchar();
  int flag = 1;
  while (!std::isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (std::isdigit(ch)) k = k * 10 + ch - '0', ch = getchar();
  Re = flag * k;
}
template <typename T>
void write(const T &Wr) {
  if (Wr < 0) {
    putchar('-'), write(-Wr);
  } else if (Wr < 10) {
    putchar(Wr + '0');
  } else {
    write(Wr / 10), putchar((Wr % 10) + '0');
  }
}

### Prompt

Please create a solution in cpp 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>
template <typename T>
void read(T &);
template <typename T>
void write(const T &);
const int iinf = 2147483647;
const long long llinf = 9223372036854775807ll;
const int N = 270000;
const int Mod = 998244353, sgn[] = {1, Mod - 1};
int pow(int a, int b, int ans = 1);
namespace Pol {
int add(int a, int b) { return (a += b) >= Mod ? a -= Mod : a; }
int sub(int a, int b) { return (a -= b) < 0 ? a += Mod : a; }
void inc(int &a, int b) { (a += b) >= Mod ? a -= Mod : a; }
void dec(int &a, int b) { (a -= b) < 0 ? a += Mod : a; }
int &reduce(int &x) { return x += x >> 31 & Mod; }
void init_Poly(int n = N);
void DIT(int *A, int lim);
void DIF(int *A, int lim);
std::vector<int> &operator+=(std::vector<int> &a, const std::vector<int> &b);
std::vector<int> mult(const std::vector<int> &A, int n,
                      const std::vector<int> &B, int m);
std::vector<int> operator*(const std::vector<int> &a,
                           const std::vector<int> &b);
unsigned long long tmp[N];
int gw[N];
}  // namespace Pol
class Matrix {
 public:
  std::vector<int> val[2][2];
  friend Matrix operator*(const Matrix &a, const Matrix &b);
};
Matrix work(int l, int r);
Matrix a[N];
int fac[N];
int seg[N], m;
int tmp[N], n;
int main() {
  Pol::init_Poly();
  read(n);
  for (int i = 1; i <= n; ++i) read(tmp[i]);
  for (int i = 1; i <= n;) {
    int now = tmp[i];
    for (int j = i; j <= i + now - 1; ++j) {
      if (tmp[j] != now) {
        puts("0");
        return 0;
      }
    }
    seg[++m] = now;
    i += now;
  }
  fac[0] = 1;
  for (int i = 1; i <= m; ++i) {
    fac[i] = 1ll * fac[i - 1] * i % Mod;
    a[i].val[1][0] = {1};
    a[i].val[0][1] = {0, 2};
    a[i].val[1][1] = {0, 1};
    if (seg[i] == 1) {
      a[i].val[0][0] = {1};
    } else {
      a[i].val[0][0] = {2};
    }
  }
  Matrix ans = work(1, m);
  int res = 0;
  for (size_t i = 0; i < ans.val[0][0].size(); ++i) {
    res = (res + 1ll * fac[m - i] * ans.val[0][0][i] % Mod * sgn[i & 1]) % Mod;
  }
  write(res), putchar('\n');
  return 0;
}
Matrix work(int l, int r) {
  if (l == r) return a[l];
  int m = (l + r) >> 1;
  return work(l, m) * work(m + 1, r);
}
Matrix operator*(const Matrix &a, const Matrix &b) {
  Matrix ans;
  using namespace Pol;
  for (int i = 0; i < 2; ++i) {
    for (int k = 0; k < 2; ++k) {
      for (int j = 0; j < 2; ++j) {
        ans.val[i][j] += a.val[i][k] * b.val[k][j];
      }
    }
  }
  return ans;
}
namespace Pol {
void DIT(int *A, int lim) {
  for (int i = 0; i < lim; ++i) tmp[i] = A[i];
  for (int l = 1; l < lim; l <<= 1) {
    unsigned long long *k = tmp;
    for (int *g = gw; k < tmp + lim; k += (l << 1), ++g) {
      for (unsigned long long *x = k; x < k + l; ++x) {
        int o = x[l] % Mod;
        x[l] = 1ll * (*x + Mod - o) * *g % Mod, *x += o;
      }
    }
  }
  int iv = pow(lim, Mod - 2);
  for (int i = 0; i < lim; ++i) A[i] = 1ll * tmp[i] % Mod * iv % Mod;
  std::reverse(A + 1, A + lim);
}
void DIF(int *A, int lim) {
  for (int i = 0; i < lim; ++i) tmp[i] = A[i];
  for (int l = lim / 2; l >= 1; l >>= 1) {
    unsigned long long *k = tmp;
    for (int *g = gw; k < tmp + lim; k += (l << 1), ++g) {
      for (unsigned long long *x = k; x < k + l; ++x) {
        int o = 1ll * x[l] * *g % Mod;
        x[l] = *x + Mod - o, *x += o;
      }
    }
  }
  for (int i = 0; i < lim; ++i) A[i] = tmp[i] % Mod;
}
std::vector<int> &operator+=(std::vector<int> &a, const std::vector<int> &b) {
  if (a.size() < b.size()) a.resize(b.size());
  for (size_t i = 0; i < a.size() && i < b.size(); ++i) inc(a[i], b[i]);
  return a;
}
std::vector<int> mult(const std::vector<int> &A, int n,
                      const std::vector<int> &B, int m) {
  int lim = 1;
  while (lim < (n + m - 1)) lim <<= 1;
  static int tA[N], tB[N];
  std::copy_n(A.begin(), n, tA), std::fill(tA + n, tA + lim, 0);
  std::copy_n(B.begin(), m, tB), std::fill(tB + m, tB + lim, 0);
  DIF(tA, lim), DIF(tB, lim);
  for (int i = 0; i < lim; ++i) tA[i] = 1ll * tA[i] * tB[i] % Mod;
  DIT(tA, lim);
  std::vector<int> ans(n + m - 1);
  std::copy_n(tA, n + m - 1, ans.begin());
  return ans;
}
std::vector<int> operator*(const std::vector<int> &a,
                           const std::vector<int> &b) {
  return mult(a, a.size(), b, b.size());
}
void init_Poly(int n) {
  int t = 1;
  while ((1 << t) < n) ++t;
  t = std::min(t - 1, 21);
  gw[0] = 1, gw[1 << t] = pow(pow(3, 119), 1 << (21 - t));
  for (int i = t; i; --i)
    gw[1 << (i - 1)] = 1ll * gw[1 << i] * gw[1 << i] % Mod;
  for (int i = 1; i < (1 << t); ++i)
    gw[i] = 1ll * gw[i & (i - 1)] * gw[i & -i] % Mod;
}
}  // namespace Pol
int pow(int a, int b, int ans) {
  while (b) {
    if (b & 1) ans = 1ll * ans * a % Mod;
    a = 1ll * a * a % Mod;
    b >>= 1;
  }
  return ans;
}
template <typename T>
void read(T &Re) {
  T k = 0;
  char ch = getchar();
  int flag = 1;
  while (!std::isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (std::isdigit(ch)) k = k * 10 + ch - '0', ch = getchar();
  Re = flag * k;
}
template <typename T>
void write(const T &Wr) {
  if (Wr < 0) {
    putchar('-'), write(-Wr);
  } else if (Wr < 10) {
    putchar(Wr + '0');
  } else {
    write(Wr / 10), putchar((Wr % 10) + '0');
  }
}

```