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 <bits/stdc++.h>

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
//const ll MOD = 1000000007;
const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
#define mp make_pair

const int MAXN = 300010;

vl fact(MAXN);

void set_fact(ll n, ll M = MOD) {
  fact[0] = fact[1] = 1;
	for (ll i = 2; i <= n; i++) {
		fact[i] = i * fact[i - 1] % M;
	}
}

class UnionFind {
public:
	int n;
	vi par; //親
	vi ran; //木の深さ
	vi num; //要素数

	UnionFind(int _n) {
		n = _n;
		par.resize(n); ran.resize(n); num.resize(n);
		for (int i = 0; i < n; i++) {
			par[i] = i; ran[i] = 0; num[i] = 1;
		}
	}

	//木の根を求める
	int find(int x) {
		if (par[x] == x) {
			return x;
		}
		else {
			return par[x] = find(par[x]);
		}
	}

	//xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x); y = find(y);
		int numsum = num[x] + num[y];
		if (x == y) {
			return;
		}
		if (ran[x]<ran[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (ran[x] == ran[y]) {
				ran[x]++;
			}
		}
		num[x] = num[y] = numsum;
	}

	//xとyが同じ集合に属するか否か
	bool same(int x, int y) {
		return find(x) == find(y);
	}

};



int main() {
  int n;
  cin >> n;
  vi a(n);
  ll t = 0;
  set_fact(n);
  rep (i, n) {
    cin >> a[i];
    a[i]--;
    if (a[i] == 0) {
      t++;
    }
  }
  if (t == n) {
    cout << fact[n] << endl;
    return 0;
  }
  vi b;
  int f = a[0];
  int i = 0;
  while (a[i] == f) {
    i++;
  }
  for (int j = i; j < n; j++) {
    b.push_back(a[j]);
  }
  for (int j = 0; j < i; j++) {
    b.push_back(a[j]);
  }
  //DEBUG_VEC(b);
  vi start(n, -1);
  int pre = -1;
  i = 0;
  while (i < n) {
    if (b[i] != pre) {
      if (start[b[i]] != -1) {
        cout << 0 << endl;
        return 0;
      }
      else {
        start[b[i]] = i;
        pre = b[i];
      }
    }
    i++;
  }

  UnionFind uf(n);
  pre = -1;
  i = 0;
  rep (j, n) {
    if (start[j] != -1) {
      continue;
    }
    while (b[i] != pre) {
      pre = b[i];
      i++;
    }
    uf.unite(b[i], j);
    i++;
  }
  
  ll ans = 1;
  ll kouho = 0;
  rep (i, n) {
    if (start[i] == -1) {
      ans *= (kouho - i);
      ans %= MOD;
      continue;
    }
    int s = start[i];
    ll cnt = 0;
    while (s < n && b[s] == i) {
      cnt++;
      s++;
    }
    if (cnt > t) {
      cout << 0 << endl;
      return 0;
    }
    if (b[(start[i] - 1 + n) % n] > i && b[s % n] > i) {
      if (cnt != t) {
        cout << 0 << endl;
        return 0;
      }
      kouho += uf.num[i] - (t - 1);
    }
    else if (b[(start[i] - 1 + n) % n] > i && b[s % n] < i) {
      kouho += cnt;
      uf.unite(i, b[s % n]);
    }
    else if (b[(start[i] - 1 + n) % n] < i && b[s % n] > i) {
      kouho += cnt;
      uf.unite(i, b[(start[i] - 1 + n) % n]);
    }
    else if (b[(start[i] - 1 + n) % n] < i && b[s % n] < i) {
      int sz1 = uf.num[b[s % n]], sz2 = b[(start[i] - 1 + n) % n];
      ans *= t - (cnt - 1);
      ans %= MOD;
      kouho -= sz1 - (t - 1);
      kouho -= sz2 - (t - 1);
      int sz = sz1 + sz2 + cnt;
      kouho += sz - (t - 1);
      uf.unite(i, b[s % n]);
      uf.unite(i, b[(start[i] - 1 + n) % n]);
    }
  }
  while (ans < 0) {
    ans += MOD;
  }
  cout << ans << endl;
}