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:
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// }}}
// #include<bits/stdc++.h>
using namespace std;
using ll = long long;

/// --- Union Find Library {{{ ///

struct UF {
  int n;
  vector< int > par;
  UF(int n) : n(n), par(n, -1) {}
  int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
  int size(int x) { return -par[find(x)]; }
  bool same(int a, int b) { return find(a) == find(b); }
  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if(a == b) return;
    if(par[a] < par[b]) swap(a, b);
    par[b] += par[a];
    par[a] = b;
  }
};

/// }}}--- ///

const int N = 3e5;

const ll mod = 998244353;

// ufはいらないと思うが楽
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  vector<int> cnt(n + 1), last(n + 1), ecas(n + 1);
  for(int i = 0; i < n; i++) cnt[a[i]]++;
  for(int i = 0; i < n-1; i++) {
    if(a[i] != a[i+1]) last[a[i]] = i, ecas[a[i]]++;
  }
  if(a[n-1] != a[0]) last[a[n-1]] = n-1, ecas[a[n-1]]++;
  for(int i = 1; i <= n; i++) if(ecas[i] >= 2) return cout << 0 << endl, 0;
  vector<pair<int, int>> v;
  for(int i = 2; i <= n; i++) if(cnt[i]) {
    last[i] += n - last[1] - 1;
    if(last[i] >= n) last[i] -= n;
    v.emplace_back(last[i], i);
  }
  int k = n - cnt[1];
  int x = cnt[1];
  if(x == n) {
    ll mochi = 1;
    for(int i = 2; i <= n; i++) mochi = mochi * i % mod;
    cout << mochi << endl;
    return 0;
  }
  int tapris = v.size();
  sort((v).begin(), (v).end());
  vector<int> rnk(n + 1);
  vector<int> used(n + 1);
  for(int i = 0; i < v.size(); i++) rnk[v[i].second] = i;
  UF uf(tapris);
  vector<pair<int, int>> uku(tapris);

  ll ans = 1;
  ll free = 0;
  for(int i = 2; i <= n; i++) {
    if(cnt[i]) {
      int qina = x - cnt[i] + 1;
      if(qina <= 0) return cout << 0 << endl, 0;
      int p = rnk[i];
      used[p] = 1;
      int ecas = cnt[i];
      if(p - 1 >= 0){ 
        if(used[p - 1]) {
          int s, t;
          tie(s, t) = uku[uf.find(p - 1)];
          free -= t;
          ecas += s;
          uf.unite(p - 1, p);
        } else {
          qina = 1;
        }
      }
      if(p + 1 < tapris) {
        if(used[p + 1]) {
          int s, t;
          tie(s, t) = uku[uf.find(p + 1)];
          free -= t;
          ecas += s;
          uf.unite(p + 1, p);
        } else {
          qina = 1;
        }
      }
      int noel;
      if(uf.same(p, tapris - 1) || uf.same(p, 0)) {
        noel = ecas;
      } else {
        noel = max(ecas - (x - 1), 0);
      }
      if(noel <= 0) return cout << 0 << endl, 0;
      uku[uf.find(p)] = make_pair(ecas, noel);
      free += noel;

      ans = ans * qina % mod;
    } else {
      int cap;
      if(free == k) {
        cap = n - 1 - (i - 2);
      } else {
        cap = free - (i - 2);
      }
      if(cap <= 0) return cout << 0 << endl, 0;
      ans = ans * cap % mod;
    }
  }
  cout << ans << endl;
  return 0;
}