#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}
int mult(int a, int b) { return a * (long long)b % mod; }
int bp(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}
const int N = 100007;
int fact[N];
struct Ans {
  vector<int> g[4];
};
class NTT {
 public:
  const static int mod = 998244353;
  const static int root = 646;
  const static int rev_root = 208611436;
  const static int root_deg = 1 << 20;
  const static int MAX_SIZE = 1 << 21;
  void add(int &a, int b) {
    a += b;
    if (a < 0) a += mod;
    if (a >= mod) a -= mod;
  }
  int sum(int a, int b) {
    add(a, b);
    return a;
  }
  int mult(int a, int b) { return a * (long long)b % mod; }
  int bp(int a, int n) {
    int res = 1;
    while (n) {
      if (n & 1) res = mult(res, a);
      a = mult(a, a);
      n >>= 1;
    }
    return res;
  }
  int rev(int a) { return bp(a, mod - 2); }
  int n;
  int a[MAX_SIZE * 2 + 7], b[MAX_SIZE * 2 + 7];
  int getReverse(int a, int k) {
    int ans = 0;
    for (int i = 0; i < k; i++)
      if ((a >> i) & 1) ans ^= (1 << (k - i - 1));
    return ans;
  }
  void ntt(int *a, int type) {
    int k = -1;
    for (int i = 0; i < 25; i++)
      if ((n >> i) & 1) {
        k = i;
        break;
      }
    for (int i = 0; i < n; i++) {
      int j = getReverse(i, k);
      if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len *= 2) {
      int w = bp(root, root_deg / len);
      if (type == -1) w = bp(rev_root, root_deg / len);
      for (int i = 0; i < n; i += len) {
        int g = 1;
        for (int j = 0; j < len / 2; j++) {
          int first = a[i + j];
          int second = mult(a[i + j + len / 2], g);
          a[i + j] = sum(first, second);
          a[i + j + len / 2] = sum(first, mod - second);
          g = mult(g, w);
        }
      }
    }
    if (type == -1) {
      int rev_n = rev(n);
      for (int i = 0; i < n; i++) a[i] = mult(a[i], rev_n);
    }
  }
  vector<int> mult(vector<int> &w1, vector<int> &w2) {
    n = 1;
    while (n < w1.size() + w2.size()) n *= 2;
    std::copy(w1.begin(), w1.end(), a);
    std::copy(w2.begin(), w2.end(), b);
    std::fill(a + w1.size(), a + n, 0);
    std::fill(b + w2.size(), b + n, 0);
    ntt(a, 1);
    ntt(b, 1);
    for (int i = 0; i < n; i++) a[i] = mult(a[i], b[i]);
    ntt(a, -1);
    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[i] = a[i];
    while (ans.size() && ans.back() == 0) ans.pop_back();
    return ans;
  }
};
vector<int> add(vector<int> a, vector<int> b) {
  vector<int> c(max(a.size(), b.size()), 0);
  for (int i = 0; i < a.size(); ++i) add(c[i], a[i]);
  for (int i = 0; i < b.size(); ++i) add(c[i], b[i]);
  return c;
}
NTT fft;
Ans solve(vector<int> &v, int l, int r) {
  if (l == r) {
    vector<int> a = {0, (v[l] > 1) + 1};
    vector<int> b = {0, 2};
    vector<int> c = {1};
    vector<int> d = {1};
    Ans ans;
    ans.g[0] = a, ans.g[1] = b, ans.g[2] = c, ans.g[3] = d;
    return ans;
  }
  int mid = (l + r) / 2;
  auto A = solve(v, l, mid), B = solve(v, mid + 1, r);
  Ans ans;
  ans.g[0] = add(fft.mult(A.g[0], B.g[0]), fft.mult(A.g[1], B.g[2]));
  ans.g[1] = add(fft.mult(A.g[0], B.g[1]), fft.mult(A.g[1], B.g[3]));
  ans.g[2] = add(fft.mult(A.g[2], B.g[0]), fft.mult(A.g[3], B.g[2]));
  ans.g[3] = add(fft.mult(A.g[2], B.g[1]), fft.mult(A.g[3], B.g[3]));
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  fact[0] = 1;
  for (int i = 1; i < N; ++i) fact[i] = mult(i, fact[i - 1]);
  int n;
  cin >> n;
  vector<int> v(n);
  for (auto &first : v) cin >> first;
  int start = 0;
  vector<int> arr;
  while (start < n) {
    if (start + v[start] > n) {
      cout << 0;
      exit(0);
    }
    for (int i = 0; i < v[start]; ++i) {
      if (v[i + start] != v[start]) {
        cout << 0;
        exit(0);
      }
    }
    arr.push_back(v[start]);
    start += v[start];
  }
  int ans = 0;
  auto res = solve(arr, 0, arr.size() - 1).g[0];
  for (int i = 0; i <= arr.size(); ++i) {
    int viol = arr.size() - i;
    if (viol % 2 == 0)
      add(ans, mult(fact[i], res[i]));
    else
      add(ans, -mult(fact[i], res[i]));
  }
  cout << ans;
}

### 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>
using namespace std;
const int mod = 998244353;
void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}
int mult(int a, int b) { return a * (long long)b % mod; }
int bp(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}
const int N = 100007;
int fact[N];
struct Ans {
  vector<int> g[4];
};
class NTT {
 public:
  const static int mod = 998244353;
  const static int root = 646;
  const static int rev_root = 208611436;
  const static int root_deg = 1 << 20;
  const static int MAX_SIZE = 1 << 21;
  void add(int &a, int b) {
    a += b;
    if (a < 0) a += mod;
    if (a >= mod) a -= mod;
  }
  int sum(int a, int b) {
    add(a, b);
    return a;
  }
  int mult(int a, int b) { return a * (long long)b % mod; }
  int bp(int a, int n) {
    int res = 1;
    while (n) {
      if (n & 1) res = mult(res, a);
      a = mult(a, a);
      n >>= 1;
    }
    return res;
  }
  int rev(int a) { return bp(a, mod - 2); }
  int n;
  int a[MAX_SIZE * 2 + 7], b[MAX_SIZE * 2 + 7];
  int getReverse(int a, int k) {
    int ans = 0;
    for (int i = 0; i < k; i++)
      if ((a >> i) & 1) ans ^= (1 << (k - i - 1));
    return ans;
  }
  void ntt(int *a, int type) {
    int k = -1;
    for (int i = 0; i < 25; i++)
      if ((n >> i) & 1) {
        k = i;
        break;
      }
    for (int i = 0; i < n; i++) {
      int j = getReverse(i, k);
      if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len *= 2) {
      int w = bp(root, root_deg / len);
      if (type == -1) w = bp(rev_root, root_deg / len);
      for (int i = 0; i < n; i += len) {
        int g = 1;
        for (int j = 0; j < len / 2; j++) {
          int first = a[i + j];
          int second = mult(a[i + j + len / 2], g);
          a[i + j] = sum(first, second);
          a[i + j + len / 2] = sum(first, mod - second);
          g = mult(g, w);
        }
      }
    }
    if (type == -1) {
      int rev_n = rev(n);
      for (int i = 0; i < n; i++) a[i] = mult(a[i], rev_n);
    }
  }
  vector<int> mult(vector<int> &w1, vector<int> &w2) {
    n = 1;
    while (n < w1.size() + w2.size()) n *= 2;
    std::copy(w1.begin(), w1.end(), a);
    std::copy(w2.begin(), w2.end(), b);
    std::fill(a + w1.size(), a + n, 0);
    std::fill(b + w2.size(), b + n, 0);
    ntt(a, 1);
    ntt(b, 1);
    for (int i = 0; i < n; i++) a[i] = mult(a[i], b[i]);
    ntt(a, -1);
    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[i] = a[i];
    while (ans.size() && ans.back() == 0) ans.pop_back();
    return ans;
  }
};
vector<int> add(vector<int> a, vector<int> b) {
  vector<int> c(max(a.size(), b.size()), 0);
  for (int i = 0; i < a.size(); ++i) add(c[i], a[i]);
  for (int i = 0; i < b.size(); ++i) add(c[i], b[i]);
  return c;
}
NTT fft;
Ans solve(vector<int> &v, int l, int r) {
  if (l == r) {
    vector<int> a = {0, (v[l] > 1) + 1};
    vector<int> b = {0, 2};
    vector<int> c = {1};
    vector<int> d = {1};
    Ans ans;
    ans.g[0] = a, ans.g[1] = b, ans.g[2] = c, ans.g[3] = d;
    return ans;
  }
  int mid = (l + r) / 2;
  auto A = solve(v, l, mid), B = solve(v, mid + 1, r);
  Ans ans;
  ans.g[0] = add(fft.mult(A.g[0], B.g[0]), fft.mult(A.g[1], B.g[2]));
  ans.g[1] = add(fft.mult(A.g[0], B.g[1]), fft.mult(A.g[1], B.g[3]));
  ans.g[2] = add(fft.mult(A.g[2], B.g[0]), fft.mult(A.g[3], B.g[2]));
  ans.g[3] = add(fft.mult(A.g[2], B.g[1]), fft.mult(A.g[3], B.g[3]));
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  fact[0] = 1;
  for (int i = 1; i < N; ++i) fact[i] = mult(i, fact[i - 1]);
  int n;
  cin >> n;
  vector<int> v(n);
  for (auto &first : v) cin >> first;
  int start = 0;
  vector<int> arr;
  while (start < n) {
    if (start + v[start] > n) {
      cout << 0;
      exit(0);
    }
    for (int i = 0; i < v[start]; ++i) {
      if (v[i + start] != v[start]) {
        cout << 0;
        exit(0);
      }
    }
    arr.push_back(v[start]);
    start += v[start];
  }
  int ans = 0;
  auto res = solve(arr, 0, arr.size() - 1).g[0];
  for (int i = 0; i <= arr.size(); ++i) {
    int viol = arr.size() - i;
    if (viol % 2 == 0)
      add(ans, mult(fact[i], res[i]));
    else
      add(ans, -mult(fact[i], res[i]));
  }
  cout << ans;
}

```