#include <bits/stdc++.h>
using namespace std;
std::mt19937 rnd(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MOD = 998244353;
const int PRIMROOT = 3;
void mlt(int& a, int b) { a = (long long)a * b % MOD; }
int pw(int x, int n) {
  int ret = 1;
  while (true) {
    if (n & 1) mlt(ret, x);
    if ((n >>= 1) == 0) return ret;
    mlt(x, x);
  }
}
struct NTT {
  void _init(int n, int& nlog, int& g, vector<int>& w) {
    assert((MOD - 1) % n == 0);
    g = pw(PRIMROOT, (MOD - 1) / n);
    nlog = 0;
    while ((1 << nlog) < n) ++nlog;
    if ((1 << nlog) != n) nlog = -1;
    w = vector<int>(n);
    w[0] = 1;
    for (int i = (1); i < (n); ++i) w[i] = (long long)w[i - 1] * g % MOD;
  }
  int fftn, fftnlog;
  int fftg;
  vector<int> fftw;
  void initfft(int n) {
    fftn = n, _init(fftn, fftnlog, fftg, fftw);
    assert(fftnlog != -1);
  }
  void fft(int* a, int n, bool inv) {
    if (n != fftn) initfft(n);
    for (int i = 1, j = n >> 1, k, l = j; i < n; j ^= k, ++i) {
      if (i < j) swap(a[i], a[j]);
      for (k = l; k & j; j ^= k, k >>= 1)
        ;
    }
    int *l, *r, *w;
    if (inv) reverse(fftw.begin() + 1, fftw.end());
    for (int hlen = 1, step = n >> 1; hlen < n; hlen <<= 1, step >>= 1) {
      for (int i = 0; i < n; i += (hlen << 1)) {
        l = a + i, r = l + hlen, w = fftw.data();
        for (int off = (0); off < (hlen); ++off) {
          int v = (long long)(*r) * (*w) % MOD;
          *r = (*l) - v;
          if (*r < 0) *r += MOD;
          *l = (*l) + v;
          if (*l >= MOD) *l -= MOD;
          ++l, ++r, w += step;
        }
      }
    }
    if (inv) reverse(fftw.begin() + 1, fftw.end());
    if (inv) {
      int mlt = pw(n, MOD - 2);
      for (int i = (0); i < (n); ++i) a[i] = (long long)a[i] * mlt % MOD;
    }
  }
  void mult(const int* a, int na, const int* b, int nb, int* c, int nc) {
    int sz = 1;
    while (sz < na + nb - 1 || sz < na || sz < nb) sz *= 2;
    vector<int> A(sz, 0), B(sz, 0);
    for (int i = (0); i < (na); ++i) A[i] = a[i];
    for (int i = (0); i < (nb); ++i) B[i] = b[i];
    fft(A.data(), sz, false);
    fft(B.data(), sz, false);
    for (int i = (0); i < (sz); ++i) A[i] = (long long)A[i] * B[i] % MOD;
    fft(A.data(), sz, true);
    for (int i = (0); i < (nc); ++i) c[i] = i < sz ? A[i] : 0;
  }
  vector<int> mult(const vector<int>& a, const vector<int>& b) {
    vector<int> c(max(0, ((int)(a).size()) + ((int)(b).size()) - 1));
    mult(a.data(), ((int)(a).size()), b.data(), ((int)(b).size()), c.data(),
         ((int)(c).size()));
    return c;
  }
};
NTT ntt;
const int MAXN = 100000;
void inc(int& a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
void dec(int& a, int b) { inc(a, MOD - b); }
int n;
int a[MAXN];
int b[MAXN], nb;
array<array<vector<int>, 2>, 2> init[2];
array<array<vector<int>, 2>, 2> trans[2];
int fac[MAXN + 1];
vector<int> mlt(const vector<int>& a, const vector<int>& b) {
  vector<int> c = ntt.mult(a, b);
  while (((int)(c).size()) >= 1 && c.back() == 0) c.pop_back();
  return c;
}
void inc(vector<int>& a, const vector<int>& b) {
  while (((int)(a).size()) < ((int)(b).size())) a.push_back(0);
  for (int i = (0); i < (((int)(b).size())); ++i) inc(a[i], b[i]);
  while (((int)(a).size()) >= 1 && a.back() == 0) a.pop_back();
}
array<array<vector<int>, 2>, 2> mlt(const array<array<vector<int>, 2>, 2>& a,
                                    const array<array<vector<int>, 2>, 2>& b) {
  array<array<vector<int>, 2>, 2> ret;
  for (int i = (0); i < (2); ++i)
    for (int j = (0); j < (2); ++j)
      for (int k = (0); k < (2); ++k) inc(ret[i][j], mlt(a[i][k], b[k][j]));
  return ret;
}
array<array<vector<int>, 2>, 2> rec(int l, int r) {
  if (l == r) return trans[b[l]];
  int m = l + (r - l) / 2;
  array<array<vector<int>, 2>, 2> lres = rec(l, m);
  array<array<vector<int>, 2>, 2> rres = rec(m + 1, r);
  return mlt(lres, rres);
}
int solve() {
  init[0][0][0] = {0, 2};
  init[1][0][1] = {0, 1};
  trans[0][0][0] = {1, 2};
  trans[0][1][0] = {2, 2};
  trans[1][0][0] = {1};
  trans[1][0][1] = {0, 1};
  trans[1][1][0] = {2};
  trans[1][1][1] = {0, 1};
  fac[0] = 1;
  for (int i = (1); i <= (n); ++i) fac[i] = (long long)fac[i - 1] * i % MOD;
  nb = 0;
  int at = 0;
  while (at < n) {
    int to = at + a[at];
    if (to > n) return 0;
    for (int i = (at); i < (to); ++i)
      if (a[i] != a[at]) return 0;
    b[nb++] = a[at] != 1 ? 0 : 1;
    at = to;
  }
  if (nb == 1) return b[0] == 0 ? 2 : 1;
  array<array<vector<int>, 2>, 2> mat = mlt(init[b[0]], rec(1, nb - 1));
  vector<int> pol;
  inc(pol, mat[0][0]);
  inc(pol, mat[0][1]);
  int ret = 0;
  for (int i = (0); i < (((int)(pol).size())); ++i) {
    int sgn = i % 2 == nb % 2 ? +1 : -1;
    int cur = (long long)fac[i] * pol[i] % MOD;
    if (sgn == +1)
      inc(ret, cur);
    else
      dec(ret, cur);
  }
  return ret;
}
void run() {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]);
  printf("%d\n", solve());
}
int main() {
  run();
  return 0;
}

### Prompt

Your challenge is to write 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;
std::mt19937 rnd(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MOD = 998244353;
const int PRIMROOT = 3;
void mlt(int& a, int b) { a = (long long)a * b % MOD; }
int pw(int x, int n) {
  int ret = 1;
  while (true) {
    if (n & 1) mlt(ret, x);
    if ((n >>= 1) == 0) return ret;
    mlt(x, x);
  }
}
struct NTT {
  void _init(int n, int& nlog, int& g, vector<int>& w) {
    assert((MOD - 1) % n == 0);
    g = pw(PRIMROOT, (MOD - 1) / n);
    nlog = 0;
    while ((1 << nlog) < n) ++nlog;
    if ((1 << nlog) != n) nlog = -1;
    w = vector<int>(n);
    w[0] = 1;
    for (int i = (1); i < (n); ++i) w[i] = (long long)w[i - 1] * g % MOD;
  }
  int fftn, fftnlog;
  int fftg;
  vector<int> fftw;
  void initfft(int n) {
    fftn = n, _init(fftn, fftnlog, fftg, fftw);
    assert(fftnlog != -1);
  }
  void fft(int* a, int n, bool inv) {
    if (n != fftn) initfft(n);
    for (int i = 1, j = n >> 1, k, l = j; i < n; j ^= k, ++i) {
      if (i < j) swap(a[i], a[j]);
      for (k = l; k & j; j ^= k, k >>= 1)
        ;
    }
    int *l, *r, *w;
    if (inv) reverse(fftw.begin() + 1, fftw.end());
    for (int hlen = 1, step = n >> 1; hlen < n; hlen <<= 1, step >>= 1) {
      for (int i = 0; i < n; i += (hlen << 1)) {
        l = a + i, r = l + hlen, w = fftw.data();
        for (int off = (0); off < (hlen); ++off) {
          int v = (long long)(*r) * (*w) % MOD;
          *r = (*l) - v;
          if (*r < 0) *r += MOD;
          *l = (*l) + v;
          if (*l >= MOD) *l -= MOD;
          ++l, ++r, w += step;
        }
      }
    }
    if (inv) reverse(fftw.begin() + 1, fftw.end());
    if (inv) {
      int mlt = pw(n, MOD - 2);
      for (int i = (0); i < (n); ++i) a[i] = (long long)a[i] * mlt % MOD;
    }
  }
  void mult(const int* a, int na, const int* b, int nb, int* c, int nc) {
    int sz = 1;
    while (sz < na + nb - 1 || sz < na || sz < nb) sz *= 2;
    vector<int> A(sz, 0), B(sz, 0);
    for (int i = (0); i < (na); ++i) A[i] = a[i];
    for (int i = (0); i < (nb); ++i) B[i] = b[i];
    fft(A.data(), sz, false);
    fft(B.data(), sz, false);
    for (int i = (0); i < (sz); ++i) A[i] = (long long)A[i] * B[i] % MOD;
    fft(A.data(), sz, true);
    for (int i = (0); i < (nc); ++i) c[i] = i < sz ? A[i] : 0;
  }
  vector<int> mult(const vector<int>& a, const vector<int>& b) {
    vector<int> c(max(0, ((int)(a).size()) + ((int)(b).size()) - 1));
    mult(a.data(), ((int)(a).size()), b.data(), ((int)(b).size()), c.data(),
         ((int)(c).size()));
    return c;
  }
};
NTT ntt;
const int MAXN = 100000;
void inc(int& a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
void dec(int& a, int b) { inc(a, MOD - b); }
int n;
int a[MAXN];
int b[MAXN], nb;
array<array<vector<int>, 2>, 2> init[2];
array<array<vector<int>, 2>, 2> trans[2];
int fac[MAXN + 1];
vector<int> mlt(const vector<int>& a, const vector<int>& b) {
  vector<int> c = ntt.mult(a, b);
  while (((int)(c).size()) >= 1 && c.back() == 0) c.pop_back();
  return c;
}
void inc(vector<int>& a, const vector<int>& b) {
  while (((int)(a).size()) < ((int)(b).size())) a.push_back(0);
  for (int i = (0); i < (((int)(b).size())); ++i) inc(a[i], b[i]);
  while (((int)(a).size()) >= 1 && a.back() == 0) a.pop_back();
}
array<array<vector<int>, 2>, 2> mlt(const array<array<vector<int>, 2>, 2>& a,
                                    const array<array<vector<int>, 2>, 2>& b) {
  array<array<vector<int>, 2>, 2> ret;
  for (int i = (0); i < (2); ++i)
    for (int j = (0); j < (2); ++j)
      for (int k = (0); k < (2); ++k) inc(ret[i][j], mlt(a[i][k], b[k][j]));
  return ret;
}
array<array<vector<int>, 2>, 2> rec(int l, int r) {
  if (l == r) return trans[b[l]];
  int m = l + (r - l) / 2;
  array<array<vector<int>, 2>, 2> lres = rec(l, m);
  array<array<vector<int>, 2>, 2> rres = rec(m + 1, r);
  return mlt(lres, rres);
}
int solve() {
  init[0][0][0] = {0, 2};
  init[1][0][1] = {0, 1};
  trans[0][0][0] = {1, 2};
  trans[0][1][0] = {2, 2};
  trans[1][0][0] = {1};
  trans[1][0][1] = {0, 1};
  trans[1][1][0] = {2};
  trans[1][1][1] = {0, 1};
  fac[0] = 1;
  for (int i = (1); i <= (n); ++i) fac[i] = (long long)fac[i - 1] * i % MOD;
  nb = 0;
  int at = 0;
  while (at < n) {
    int to = at + a[at];
    if (to > n) return 0;
    for (int i = (at); i < (to); ++i)
      if (a[i] != a[at]) return 0;
    b[nb++] = a[at] != 1 ? 0 : 1;
    at = to;
  }
  if (nb == 1) return b[0] == 0 ? 2 : 1;
  array<array<vector<int>, 2>, 2> mat = mlt(init[b[0]], rec(1, nb - 1));
  vector<int> pol;
  inc(pol, mat[0][0]);
  inc(pol, mat[0][1]);
  int ret = 0;
  for (int i = (0); i < (((int)(pol).size())); ++i) {
    int sgn = i % 2 == nb % 2 ? +1 : -1;
    int cur = (long long)fac[i] * pol[i] % MOD;
    if (sgn == +1)
      inc(ret, cur);
    else
      dec(ret, cur);
  }
  return ret;
}
void run() {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]);
  printf("%d\n", solve());
}
int main() {
  run();
  return 0;
}

```