#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = getchar();
  int nega = 1;
  while (!isdigit(ch)) {
    if (ch == '-') nega = -1;
    ch = getchar();
  }
  int ans = 0;
  while (isdigit(ch)) {
    ans = ans * 10 + ch - 48;
    ch = getchar();
  }
  if (nega == -1) return -ans;
  return ans;
}
void print(vector<int> x) {
  for (int i = 0; i < (int)x.size(); i++)
    printf("%d%c", x[i], " \n"[i == (int)x.size() - 1]);
}
inline int add(int x, int y) {
  return x + y >= 998244353 ? x + y - 998244353 : x + y;
}
inline int add(int x, int y, int z) { return add(add(x, y), z); }
inline int sub(int x, int y) { return x - y < 0 ? x - y + 998244353 : x - y; }
inline int mul(int x, int y) { return 1LL * x * y % 998244353; }
inline int mul(int x, int y, int z) { return mul(mul(x, y), z); }
int qpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    x = mul(x, x);
    y >>= 1;
  }
  return ans;
}
int Inv(int x) { return qpow(x, 998244353 - 2); }
namespace Poly {
vector<int> rev, rt, one(1, 1);
int __inv[2000005];
const int G = 3;
void Init_Inv() {
  __inv[0] = __inv[1] = 1;
  for (int i = 2; i <= 2000000; i++)
    __inv[i] = mul(998244353 - 998244353 / i, __inv[998244353 % i]);
}
vector<int> operator+(vector<int> a, vector<int> b) {
  int n = max(a.size(), b.size());
  a.resize(n), b.resize(n);
  for (int i = 0; i < n; i++) a[i] = add(a[i], b[i]);
  return a;
}
vector<int> operator-(vector<int> a, vector<int> b) {
  int n = max(a.size(), b.size());
  a.resize(n), b.resize(n);
  for (int i = 0; i < n; i++) a[i] = sub(a[i], b[i]);
  return a;
}
void init(int B) {
  int n = 1 << B;
  rev.resize(n), rt.resize(n);
  for (int i = 1; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (B - 1));
  for (int mid = 1; mid < n; mid <<= 1) {
    int w = qpow(G, (998244353 - 1) / (mid << 1));
    rt[mid] = 1;
    for (int i = 1; i < mid; i++) rt[mid + i] = mul(rt[mid + i - 1], w);
  }
}
void ntt(vector<int> &a, int B) {
  for (int i = 0; i < (int)a.size(); i++)
    if (rev[i] > i) swap(a[rev[i]], a[i]);
  for (int i = 1; i < 1 << B; i <<= 1) {
    for (int j = 0; j < 1 << B; j += i << 1) {
      for (int k = 0; k < i; k++) {
        int x = a[j + k], y = mul(a[i + j + k], rt[i + k]);
        a[j + k] = add(x, y), a[i + j + k] = sub(x, y);
      }
    }
  }
}
void idft(vector<int> &a, int B) {
  reverse(a.begin() + 1, a.end());
  ntt(a, B);
  int I = Inv(1 << B);
  for (int i = 0; i < (int)a.size(); i++) a[i] = mul(a[i], I);
}
vector<int> operator*(vector<int> x, vector<int> y) {
  int n = x.size() + y.size() - 1;
  int B = 0;
  while (1 << B < n) B++;
  x.resize(1 << B), y.resize(1 << B);
  init(B);
  ntt(x, B), ntt(y, B);
  for (int i = 0; i < 1 << B; i++) x[i] = mul(x[i], y[i]);
  idft(x, B);
  x.resize(n);
  return x;
}
};  // namespace Poly
using namespace Poly;
const int i2 = (998244353 + 1) / 2;
int fac[100005], inv[100005], ifac[100005];
int norm(int x) { return ((x % 998244353) + 998244353) % 998244353; }
void init() {
  fac[0] = 1;
  for (int i = 1; i < 100005; i++) fac[i] = mul(fac[i - 1], i);
  inv[0] = inv[1] = 1;
  for (int i = 2; i < 100005; i++)
    inv[i] = mul(998244353 - 998244353 / i, inv[998244353 % i]);
  ifac[0] = 1;
  for (int i = 1; i < 100005; i++) ifac[i] = mul(ifac[i - 1], inv[i]);
}
int C(int x, int y) { return x >= y ? mul(fac[x], ifac[x - y], ifac[y]) : 0; }
int a[100005], b[100005], n, m;
struct Node {
  vector<int> a[2][2];
  int coef;
  Node() {
    coef = 0;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) a[i][j].resize(1);
  }
};
vector<int> shift(vector<int> a) {
  int n = (int)a.size() + 1;
  vector<int> ans(n);
  for (int i = 0; i < (int)a.size(); i++) ans[i + 1] = a[i];
  return ans;
}
vector<int> mul(vector<int> a, int b) {
  b = norm(b);
  for (int i = 0; i < (int)a.size(); i++) a[i] = mul(a[i], b);
  return a;
}
int sgn(int x) {
  if (x > 0)
    return 1;
  else if (x == 0)
    return 0;
  else
    return -1;
}
Node solve(int l, int r) {
  if (l == r) {
    Node ans;
    ans.coef = a[l] > 1 ? 2 : 1;
    return ans;
  }
  int mid = (l + r) / 2;
  Node A = solve(l, mid), B = solve(mid + 1, r);
  Node ans;
  ans.coef = sgn(A.coef) * sgn(B.coef) * -2;
  int c = abs(A.coef), d = abs(B.coef);
  int p = c > 1, q = d > 1;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      for (int c = 0; c < 2; c++)
        for (int d = 0; d < 2; d++) {
          vector<int> r = A.a[i][j] * B.a[c][d];
          ans.a[i][d] = ans.a[i][d] + shift(r);
          if (j == 1 && c == 1) r = mul(r, i2);
          if (j == 0 && c == 0) r = mul(r, 2);
          ans.a[i][d] = ans.a[i][d] - r;
        }
    }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      ans.a[i][q] = ans.a[i][q] + shift(mul(A.a[i][j], B.coef));
      int qwq = (j == 0) ? 2 : 1;
      qwq *= sgn(B.coef);
      ans.a[i][1] = ans.a[i][1] - mul(A.a[i][j], qwq);
    }
  for (int c = 0; c < 2; c++)
    for (int d = 0; d < 2; d++) {
      ans.a[p][d] = ans.a[p][d] + shift(mul(B.a[c][d], A.coef));
      int qwq = (c == 0) ? 2 : 1;
      qwq *= sgn(A.coef);
      ans.a[1][d] = ans.a[1][d] - mul(B.a[c][d], qwq);
    }
  c = c > 1, d = d > 1;
  if (ans.a[c][d].size() < 2) ans.a[c][d].resize(2);
  ans.a[c][d][1] = add(ans.a[c][d][1], norm(A.coef * B.coef));
  return ans;
}
signed main() {
  init();
  cin >> n;
  for (int i = 1; i <= n; i++) b[i] = read();
  for (int i = 1; i <= n;) {
    a[++m] = b[i];
    for (int j = 0; j < b[i]; j++)
      if (b[i + j] != b[i]) return cout << "0\n", 0;
    i += b[i];
  }
  Node res = solve(1, m);
  int Ans = 0;
  vector<int> ans = res.a[0][0] + res.a[0][1] + res.a[1][0] + res.a[1][1];
  ans[0] = add(ans[0], res.coef);
  for (int i = 0; i < (int)ans.size(); i++)
    Ans = add(Ans, mul(fac[i + 1], ans[i]));
  cout << Ans << endl;
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
inline int read() {
  char ch = getchar();
  int nega = 1;
  while (!isdigit(ch)) {
    if (ch == '-') nega = -1;
    ch = getchar();
  }
  int ans = 0;
  while (isdigit(ch)) {
    ans = ans * 10 + ch - 48;
    ch = getchar();
  }
  if (nega == -1) return -ans;
  return ans;
}
void print(vector<int> x) {
  for (int i = 0; i < (int)x.size(); i++)
    printf("%d%c", x[i], " \n"[i == (int)x.size() - 1]);
}
inline int add(int x, int y) {
  return x + y >= 998244353 ? x + y - 998244353 : x + y;
}
inline int add(int x, int y, int z) { return add(add(x, y), z); }
inline int sub(int x, int y) { return x - y < 0 ? x - y + 998244353 : x - y; }
inline int mul(int x, int y) { return 1LL * x * y % 998244353; }
inline int mul(int x, int y, int z) { return mul(mul(x, y), z); }
int qpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    x = mul(x, x);
    y >>= 1;
  }
  return ans;
}
int Inv(int x) { return qpow(x, 998244353 - 2); }
namespace Poly {
vector<int> rev, rt, one(1, 1);
int __inv[2000005];
const int G = 3;
void Init_Inv() {
  __inv[0] = __inv[1] = 1;
  for (int i = 2; i <= 2000000; i++)
    __inv[i] = mul(998244353 - 998244353 / i, __inv[998244353 % i]);
}
vector<int> operator+(vector<int> a, vector<int> b) {
  int n = max(a.size(), b.size());
  a.resize(n), b.resize(n);
  for (int i = 0; i < n; i++) a[i] = add(a[i], b[i]);
  return a;
}
vector<int> operator-(vector<int> a, vector<int> b) {
  int n = max(a.size(), b.size());
  a.resize(n), b.resize(n);
  for (int i = 0; i < n; i++) a[i] = sub(a[i], b[i]);
  return a;
}
void init(int B) {
  int n = 1 << B;
  rev.resize(n), rt.resize(n);
  for (int i = 1; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (B - 1));
  for (int mid = 1; mid < n; mid <<= 1) {
    int w = qpow(G, (998244353 - 1) / (mid << 1));
    rt[mid] = 1;
    for (int i = 1; i < mid; i++) rt[mid + i] = mul(rt[mid + i - 1], w);
  }
}
void ntt(vector<int> &a, int B) {
  for (int i = 0; i < (int)a.size(); i++)
    if (rev[i] > i) swap(a[rev[i]], a[i]);
  for (int i = 1; i < 1 << B; i <<= 1) {
    for (int j = 0; j < 1 << B; j += i << 1) {
      for (int k = 0; k < i; k++) {
        int x = a[j + k], y = mul(a[i + j + k], rt[i + k]);
        a[j + k] = add(x, y), a[i + j + k] = sub(x, y);
      }
    }
  }
}
void idft(vector<int> &a, int B) {
  reverse(a.begin() + 1, a.end());
  ntt(a, B);
  int I = Inv(1 << B);
  for (int i = 0; i < (int)a.size(); i++) a[i] = mul(a[i], I);
}
vector<int> operator*(vector<int> x, vector<int> y) {
  int n = x.size() + y.size() - 1;
  int B = 0;
  while (1 << B < n) B++;
  x.resize(1 << B), y.resize(1 << B);
  init(B);
  ntt(x, B), ntt(y, B);
  for (int i = 0; i < 1 << B; i++) x[i] = mul(x[i], y[i]);
  idft(x, B);
  x.resize(n);
  return x;
}
};  // namespace Poly
using namespace Poly;
const int i2 = (998244353 + 1) / 2;
int fac[100005], inv[100005], ifac[100005];
int norm(int x) { return ((x % 998244353) + 998244353) % 998244353; }
void init() {
  fac[0] = 1;
  for (int i = 1; i < 100005; i++) fac[i] = mul(fac[i - 1], i);
  inv[0] = inv[1] = 1;
  for (int i = 2; i < 100005; i++)
    inv[i] = mul(998244353 - 998244353 / i, inv[998244353 % i]);
  ifac[0] = 1;
  for (int i = 1; i < 100005; i++) ifac[i] = mul(ifac[i - 1], inv[i]);
}
int C(int x, int y) { return x >= y ? mul(fac[x], ifac[x - y], ifac[y]) : 0; }
int a[100005], b[100005], n, m;
struct Node {
  vector<int> a[2][2];
  int coef;
  Node() {
    coef = 0;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) a[i][j].resize(1);
  }
};
vector<int> shift(vector<int> a) {
  int n = (int)a.size() + 1;
  vector<int> ans(n);
  for (int i = 0; i < (int)a.size(); i++) ans[i + 1] = a[i];
  return ans;
}
vector<int> mul(vector<int> a, int b) {
  b = norm(b);
  for (int i = 0; i < (int)a.size(); i++) a[i] = mul(a[i], b);
  return a;
}
int sgn(int x) {
  if (x > 0)
    return 1;
  else if (x == 0)
    return 0;
  else
    return -1;
}
Node solve(int l, int r) {
  if (l == r) {
    Node ans;
    ans.coef = a[l] > 1 ? 2 : 1;
    return ans;
  }
  int mid = (l + r) / 2;
  Node A = solve(l, mid), B = solve(mid + 1, r);
  Node ans;
  ans.coef = sgn(A.coef) * sgn(B.coef) * -2;
  int c = abs(A.coef), d = abs(B.coef);
  int p = c > 1, q = d > 1;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      for (int c = 0; c < 2; c++)
        for (int d = 0; d < 2; d++) {
          vector<int> r = A.a[i][j] * B.a[c][d];
          ans.a[i][d] = ans.a[i][d] + shift(r);
          if (j == 1 && c == 1) r = mul(r, i2);
          if (j == 0 && c == 0) r = mul(r, 2);
          ans.a[i][d] = ans.a[i][d] - r;
        }
    }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      ans.a[i][q] = ans.a[i][q] + shift(mul(A.a[i][j], B.coef));
      int qwq = (j == 0) ? 2 : 1;
      qwq *= sgn(B.coef);
      ans.a[i][1] = ans.a[i][1] - mul(A.a[i][j], qwq);
    }
  for (int c = 0; c < 2; c++)
    for (int d = 0; d < 2; d++) {
      ans.a[p][d] = ans.a[p][d] + shift(mul(B.a[c][d], A.coef));
      int qwq = (c == 0) ? 2 : 1;
      qwq *= sgn(A.coef);
      ans.a[1][d] = ans.a[1][d] - mul(B.a[c][d], qwq);
    }
  c = c > 1, d = d > 1;
  if (ans.a[c][d].size() < 2) ans.a[c][d].resize(2);
  ans.a[c][d][1] = add(ans.a[c][d][1], norm(A.coef * B.coef));
  return ans;
}
signed main() {
  init();
  cin >> n;
  for (int i = 1; i <= n; i++) b[i] = read();
  for (int i = 1; i <= n;) {
    a[++m] = b[i];
    for (int j = 0; j < b[i]; j++)
      if (b[i + j] != b[i]) return cout << "0\n", 0;
    i += b[i];
  }
  Node res = solve(1, m);
  int Ans = 0;
  vector<int> ans = res.a[0][0] + res.a[0][1] + res.a[1][0] + res.a[1][1];
  ans[0] = add(ans[0], res.coef);
  for (int i = 0; i < (int)ans.size(); i++)
    Ans = add(Ans, mul(fac[i + 1], ans[i]));
  cout << Ans << endl;
  return 0;
}

```