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 <vector>
#include <set>
#define llint long long
#define inf 1000000000
#define mod 998244353

using namespace std;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

llint n;
llint a[300005];
llint l[300005], r[300005];
llint R[300005];
UnionFind uf(300005);
set<llint> S;

int main(void)
{
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	
	for(int i = 0; i < n-1; i++){
		if(a[i] == a[i+1]) uf.unite(i, i+1);
	}
	if(a[0] == a[n-1]) uf.unite(0, n-1);
	
	llint len = 0;
	for(int i = 1; i <= n; i++) R[i] = -1;
	for(int i = 0; i < n; i++){
		if(R[a[i]] != -1 && R[a[i]] != uf.root(i)){
			cout << 0 << endl;
			return 0;
		}
		R[a[i]] = uf.root(i);
		if(a[i] == 1) len++;
	}
	if(len == n){
		llint ans = 1;
		for(int i = 1; i <= n; i++) ans *= i, ans %= mod;
		cout << ans << endl;
		return 0;
	}
	
	for(int i = 1; i <= n; i++) l[i] = inf, r[i] = -inf;
	for(llint i = 0; i < n; i++){
		l[a[i]] = min(l[a[i]], i);
		r[a[i]] = max(r[a[i]], i);
	}
	if(a[0] == a[n-1]){
		for(int i = 0; i < n; i++){
			if(a[i] != a[0]){
				r[a[0]] = i-1;
				break;
			}
		}
		for(int i = n-1; i >= 0; i--){
			if(a[i] != a[n-1]){
				l[a[n-1]] = i+1;
				break;
			}
		}
		if(l[a[0]] > r[a[0]]) r[a[0]] += n;
	}
	//for(int i = 1; i <= n; i++) cout << l[i] << " " << r[i] << endl;
	
	for(int i = 1; i <= n; i++){
		if(l[i] == inf) continue;
		if(r[i]-l[i]+1 > len){
			cout << 0 << endl;
			return 0;
		}
	}
	
	llint ans = 1, valid = 0;
	for(int i = l[1]; i <= r[1]; i++) S.insert(i%n);
	for(int i = 2; i <= n; i++){
		if(l[i] == inf){
			if(valid <= 0){
				cout << 0 << endl;
				return 0;
			}
			ans *= valid, ans %= mod;
			valid--;
			continue;
		}
		bool lflag = S.count((l[i]-1+n)%n), rflag = S.count((r[i]+1)%n);
		if(!lflag && !rflag){
			if(len != r[i]-l[i]+1){
				cout << 0 << endl;
				return 0;
			}
		}
		else if(!lflag || !rflag) valid += r[i]-l[i];
		else{
			ans *= len - (r[i]-l[i]+1) + 1, ans %= mod;
			valid += len-1+(r[i]-l[i]+1)-1;
		}
		for(int j = l[i]; j <= r[i]; j++) S.insert(j%n);
		//cout << i << " " << S.size() << " " << valid << " " << ans << endl;
	}
	cout << ans << endl;
	
	return 0;
}