Problem: You are given a sequence of N integers: A_1,A_2,...,A_N.

Find the number of permutations p_1,p_2,...,p_N of 1,2,...,N that can be changed to A_1,A_2,...,A_N by performing the following operation some number of times (possibly zero), modulo 998244353:

* For each 1\leq i\leq N, let q_i=min(p_{i-1},p_{i}), where p_0=p_N. Replace the sequence p with the sequence q.

Constraints

* 1 \leq N \leq 3 × 10^5
* 1 \leq A_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1
:
A_N


Output

Print the number of the sequences that satisfy the condition, modulo 998244353.

Examples

Input

3
1
2
1


Output

2


Input

5
3
1
4
1
5


Output

0


Input

8
4
4
4
1
1
1
2
2


Output

24


Input

6
1
1
6
2
2
2


Output

0

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

const int mod = 998244353;

struct mint {
  int n;
  mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { return (a.n += b.n) >= mod ? a.n - mod : a.n; }
mint operator-(mint a, mint b) { return (a.n -= b.n) < 0 ? a.n + mod : a.n; }
mint operator*(mint a, mint b) { return 1LL * a.n * b.n % mod; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

struct IntervalSet {
  map<int, int> mp;
  int K;
  int n;
  int sum = 0;

  IntervalSet(int n_, int K_) : n(n_), K(K_) {}

  void insert(int l, int r) {
    if (r <= l) return;
    auto it = mp.lower_bound(l);
    if (it != mp.end() && r >= it->second) {
      l = min(l, it->second);
      r = max(r, it->first);
      if (it->second >= n && it->second < n * 2) {
        sum -= max(0, it->first - it->second - K + 1);
      }
      mp.erase(it++);
      while (it != mp.end()) {
        if (r >= it->second) {
          r = max(r, it->first);
          if (it->second >= n && it->second < n * 2) {
            sum -= max(0, it->first - it->second - K + 1);
          }
          mp.erase(it++);
        } else break;
      }
    }
    if (l >= n && l < n * 2) {
      sum += max(0, r - l - K + 1);
    }
    mp[r] = l;
  }

  void print() {
    for (auto e : mp) {
      cout << e.second << ' ' << e.first << endl;
    }
    cout << endl;
  }
};

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  if (count(a.begin(), a.end(), 0) == 0) {
    cerr << "case 1" << endl;
    cout << 0 << endl;
    return 0;
  }
  int k = -1;
  for (int i = 0; i < n; i++) {
    if (a[(i - 1 + n) % n] != 0 && a[i] == 0) {
      k = i;
      break;
    }
  }
  if (k == -1) {
    mint ans = 1;
    for (int i = 1; i <= n; i++) {
      ans *= i;
    }
    cout << ans << endl;
    return 0;
  }
  rotate(a.begin(), a.begin() + k, a.end());
  vector<pair<int, int>> b;
  vector<int> pos(n);
  vector<int> len(n);
  int i = 0;
  while (i < n) {
    int j = i;
    while (i < n && a[i] == a[j]) i++;
    if (len[a[j]] != 0) {
      cerr << "case 2" << endl;
      cout << 0 << endl;
      return 0;
    }
    pos[a[j]] = j;
    len[a[j]] = i - j;
    b.emplace_back(a[j], i - j);
  }
  for (int i = 0; i < n; i++) {
    if (len[0] < len[i]) {
      cerr << "case 3" << endl;
      cout << 0 << endl;
      return 0;
    }
  }
  int K = len[0];
  IntervalSet st(n, K);
  mint ans = 1;
  for (int i = 0; i < n; i++) {
    if (len[i] == 0) {
      if (st.sum == 0) {
        ans *= max(0, n - i);
      } else {
        ans *= max(0, st.sum - i);
      }
    } else {
      auto it = st.mp.find(pos[i] + n);
      auto it2 = st.mp.upper_bound(pos[i] + n);
      int total = 0;
      if (it != st.mp.end()) {
        total += min(K - len[i], it->first - it->second);
      }
      if (it2 != st.mp.end() && it2->second == pos[i] + len[i] + n) {
        total += min(K - len[i], it2->first - it2->second);
      }
      ans *= max(0, total - (K - len[i]) + 1);
      st.insert(pos[i], pos[i] + len[i]);
      st.insert(pos[i] + n, pos[i] + len[i] + n);
      st.insert(pos[i] + n * 2, pos[i] + len[i] + n * 2);
    }    
  }
  cout << ans << endl;
}