#include <bits/stdc++.h>
using namespace std;
template <class T>
bool checkmax(T &a, T b) {
  return b > a ? a = b, 1 : 0;
}
template <class T>
bool checkmin(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
const int N = 100005, mod = 998244353;
void add(int &a, int b) {
  a += b;
  (a >= mod) && (a -= mod);
}
void mul(int &a, int b) { a = (long long)a * b % mod; }
int Add(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}
int Sub(int a, int b) {
  a -= b;
  return a < 0 ? a + mod : a;
}
int Mul(int a, int b) { return (long long)a * b % mod; }
int qpow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) mul(ans, a);
    mul(a, a);
    b >>= 1;
  }
  return ans;
}
int n, m = 0;
int a[N], seq[N];
int pw2[N], fac[N];
void prepare(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = Mul(fac[i - 1], i);
  pw2[0] = 1;
  for (int i = 1; i <= n; ++i) pw2[i] = Mul(pw2[i - 1], 2);
}
void init() {
  prepare(100000);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n;) {
    if (i + a[i] - 1 > n) {
      printf("0\n");
      exit(0);
    };
    for (int j = i; j <= i + a[i] - 1; ++j) {
      if (a[j] != a[i]) {
        printf("0\n");
        exit(0);
      };
    }
    seq[++m] = a[i];
    i += a[i];
  }
}
namespace fft {
vector<int> w[22];
int rev[1 << 18];
void prepare(int n) {
  for (int i = 1; i <= n; ++i) {
    w[i].resize(1 << i);
    w[i][0] = 1, w[i][1] = qpow(3, (mod - 1) >> i);
    for (int j = 2; j < (1 << i); ++j) {
      w[i][j] = Mul(w[i][j - 1], w[i][1]);
    }
  }
}
void init(int n) {
  for (int i = 0; i < n; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
}
void dft(int *a, int n) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int mid = 1, rnd = 1; mid < n; mid <<= 1, ++rnd) {
    for (int i = 0; i < n; i += (mid << 1)) {
      int *W = &w[rnd][0], *l = a + i, *r = a + i + mid, t;
      for (int j = 0; j < mid; ++j, ++W, ++l, ++r) {
        t = Mul(*W, *r);
        *r = Sub(*l, t);
        add(*l, t);
      }
    }
  }
}
void idft(int *a, int n) {
  dft(a, n);
  reverse(a + 1, a + n);
  int I = qpow(n, mod - 2);
  for (int i = 0; i < n; ++i) mul(a[i], I);
}
}  // namespace fft
using fft::dft;
using fft::idft;
struct mat {
  vector<int> a[2][2];
} p[N];
vector<int> operator+(vector<int> a, vector<int> b) {
  a.resize(max((int)a.size(), (int)b.size()));
  for (int i = 0; i < (int)b.size(); ++i) add(a[i], b[i]);
  return a;
}
vector<int> operator*(vector<int> a, int b) {
  for (int i = 0; i < (int)a.size(); ++i) mul(a[i], b);
  return a;
}
vector<int> operator*(vector<int> a, vector<int> b) {
  if (a.empty() || b.empty()) return vector<int>();
  int rn = (int)a.size() + (int)b.size() - 1, n = 1;
  while (n < rn) n <<= 1;
  fft::init(n);
  a.resize(n);
  b.resize(n);
  dft(&a[0], n);
  dft(&b[0], n);
  for (int i = 0; i < n; ++i) mul(a[i], b[i]);
  idft(&a[0], n);
  a.resize(rn);
  return a;
}
mat operator*(mat a, mat b) {
  mat c;
  c.a[0][0] = a.a[0][0] * b.a[0][0] + a.a[0][1] * b.a[1][0];
  c.a[0][1] = a.a[0][0] * b.a[0][1] + a.a[0][1] * b.a[1][1];
  c.a[1][0] = a.a[1][0] * b.a[0][0] + a.a[1][1] * b.a[1][0];
  c.a[1][1] = a.a[1][0] * b.a[0][1] + a.a[1][1] * b.a[1][1];
  return c;
}
mat divi(int l, int r) {
  if (l == r) return p[l];
  int mid = (l + r) >> 1;
  return divi(l, mid) * divi(mid + 1, r);
}
void solve() {
  fft::prepare(18);
  vector<int> ii = {0}, ia = {1}, ib = {2}, ic = {0, 1}, id = {2, 1},
              ie = {1, 1};
  if (seq[1] == 1)
    p[1].a[0][1] = ia;
  else
    p[1].a[0][0] = ia;
  for (int i = 2; i <= m; ++i) {
    if (seq[i] == 1)
      p[i] = (mat){ic, ib, ic, ia};
    else
      p[i] = (mat){id, ii, ie, ii};
  }
  mat o = divi(1, m);
  vector<int> F = o.a[0][0] * 2 + o.a[0][1];
  int ans = 0;
  for (int i = 0; i < (int)F.size(); ++i) {
    int p = Mul(fac[m - i], F[i]);
    if (i & 1) p = (p == 0 ? 0 : mod - p);
    add(ans, p);
  }
  printf("%d\n", ans);
}
int main() {
  init();
  solve();
  return 0;
}

### Prompt

Create a solution in cpp for 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;
template <class T>
bool checkmax(T &a, T b) {
  return b > a ? a = b, 1 : 0;
}
template <class T>
bool checkmin(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
const int N = 100005, mod = 998244353;
void add(int &a, int b) {
  a += b;
  (a >= mod) && (a -= mod);
}
void mul(int &a, int b) { a = (long long)a * b % mod; }
int Add(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}
int Sub(int a, int b) {
  a -= b;
  return a < 0 ? a + mod : a;
}
int Mul(int a, int b) { return (long long)a * b % mod; }
int qpow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) mul(ans, a);
    mul(a, a);
    b >>= 1;
  }
  return ans;
}
int n, m = 0;
int a[N], seq[N];
int pw2[N], fac[N];
void prepare(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = Mul(fac[i - 1], i);
  pw2[0] = 1;
  for (int i = 1; i <= n; ++i) pw2[i] = Mul(pw2[i - 1], 2);
}
void init() {
  prepare(100000);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n;) {
    if (i + a[i] - 1 > n) {
      printf("0\n");
      exit(0);
    };
    for (int j = i; j <= i + a[i] - 1; ++j) {
      if (a[j] != a[i]) {
        printf("0\n");
        exit(0);
      };
    }
    seq[++m] = a[i];
    i += a[i];
  }
}
namespace fft {
vector<int> w[22];
int rev[1 << 18];
void prepare(int n) {
  for (int i = 1; i <= n; ++i) {
    w[i].resize(1 << i);
    w[i][0] = 1, w[i][1] = qpow(3, (mod - 1) >> i);
    for (int j = 2; j < (1 << i); ++j) {
      w[i][j] = Mul(w[i][j - 1], w[i][1]);
    }
  }
}
void init(int n) {
  for (int i = 0; i < n; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
}
void dft(int *a, int n) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int mid = 1, rnd = 1; mid < n; mid <<= 1, ++rnd) {
    for (int i = 0; i < n; i += (mid << 1)) {
      int *W = &w[rnd][0], *l = a + i, *r = a + i + mid, t;
      for (int j = 0; j < mid; ++j, ++W, ++l, ++r) {
        t = Mul(*W, *r);
        *r = Sub(*l, t);
        add(*l, t);
      }
    }
  }
}
void idft(int *a, int n) {
  dft(a, n);
  reverse(a + 1, a + n);
  int I = qpow(n, mod - 2);
  for (int i = 0; i < n; ++i) mul(a[i], I);
}
}  // namespace fft
using fft::dft;
using fft::idft;
struct mat {
  vector<int> a[2][2];
} p[N];
vector<int> operator+(vector<int> a, vector<int> b) {
  a.resize(max((int)a.size(), (int)b.size()));
  for (int i = 0; i < (int)b.size(); ++i) add(a[i], b[i]);
  return a;
}
vector<int> operator*(vector<int> a, int b) {
  for (int i = 0; i < (int)a.size(); ++i) mul(a[i], b);
  return a;
}
vector<int> operator*(vector<int> a, vector<int> b) {
  if (a.empty() || b.empty()) return vector<int>();
  int rn = (int)a.size() + (int)b.size() - 1, n = 1;
  while (n < rn) n <<= 1;
  fft::init(n);
  a.resize(n);
  b.resize(n);
  dft(&a[0], n);
  dft(&b[0], n);
  for (int i = 0; i < n; ++i) mul(a[i], b[i]);
  idft(&a[0], n);
  a.resize(rn);
  return a;
}
mat operator*(mat a, mat b) {
  mat c;
  c.a[0][0] = a.a[0][0] * b.a[0][0] + a.a[0][1] * b.a[1][0];
  c.a[0][1] = a.a[0][0] * b.a[0][1] + a.a[0][1] * b.a[1][1];
  c.a[1][0] = a.a[1][0] * b.a[0][0] + a.a[1][1] * b.a[1][0];
  c.a[1][1] = a.a[1][0] * b.a[0][1] + a.a[1][1] * b.a[1][1];
  return c;
}
mat divi(int l, int r) {
  if (l == r) return p[l];
  int mid = (l + r) >> 1;
  return divi(l, mid) * divi(mid + 1, r);
}
void solve() {
  fft::prepare(18);
  vector<int> ii = {0}, ia = {1}, ib = {2}, ic = {0, 1}, id = {2, 1},
              ie = {1, 1};
  if (seq[1] == 1)
    p[1].a[0][1] = ia;
  else
    p[1].a[0][0] = ia;
  for (int i = 2; i <= m; ++i) {
    if (seq[i] == 1)
      p[i] = (mat){ic, ib, ic, ia};
    else
      p[i] = (mat){id, ii, ie, ii};
  }
  mat o = divi(1, m);
  vector<int> F = o.a[0][0] * 2 + o.a[0][1];
  int ans = 0;
  for (int i = 0; i < (int)F.size(); ++i) {
    int p = Mul(fac[m - i], F[i]);
    if (i & 1) p = (p == 0 ? 0 : mod - p);
    add(ans, p);
  }
  printf("%d\n", ans);
}
int main() {
  init();
  solve();
  return 0;
}

```