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>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 300000 + 10;
const int MOD = 998244353;
const int LOG = 20;
const int INF = 1000000010;
const int delta = 11353;

int n, b[N], a[N], fac[N], cnt[N], L[N], R[N], l[N], r[N], mx[N], num[N], ps[N], C[N];
multiset<int> st;
vi vl[N], vr[N], koj[N];

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	fac[0] = 1;
	for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * 1ll * i % MOD;
	for (int i = 0; i < n; i++) cin >> b[i];
	int Fi = -1;
	for (int i = 0; i < n; i++){
		if (b[i] == 1 && Fi == -1) Fi = i;
	}
	if (Fi == -1) return cout << 0, 0;
	if (b[0] == 1 && b[n - 1] == 1){
		int cnt2 = 0;
		for (int i = 0; i < n; i++) if (b[i] == 1) cnt2++;
		if (cnt2 == n) return cout << fac[n], 0;
		for (int i = n - 1; i >= 0; i--){
			if (b[i] != 1){
				Fi = i + 1;
				break;
			}
		}
	}	
	for (int i = 0; i < n; i++){
		a[i + 1] = b[(i + Fi) % n];
		if (L[a[i + 1]] == 0) L[a[i + 1]] = i + 1;
		R[a[i + 1]] = i + 1;
		cnt[a[i + 1]]++;
	}
	//for (int i = 1; i <= n; i++) cout << a[i] << '\n';
	for (int i = 1; i <= n; i++) if(cnt[i] != 0 && R[i] - L[i] + 1!= cnt[i]) return cout << 0, 0;
	if (cnt[1] == 0) return cout << 0, 0;
	int d = cnt[1] - 1;
	for (int i = 1; i <= n; i++){
		vl[max(1, i - d)].pb(a[i]);
		vr[i].pb(a[i]);
	}	
	for (int i = 1; i <= n; i++){
		for (auto u:vl[i]) st.insert(u);
		mx[i] = *st.rbegin();
		for (auto u:vr[i]) st.erase(st.find(u));
		//cout << mx[i] << ' ';
		C[mx[i]] ++;
		koj[mx[i]].pb(i);
	}
	for (int i = 1; i <= n; i++) koj[i].pb(INF);
	memset(r, 31, sizeof r);
	for (int i = 1; i <= n; i++){
		l[a[i]] = max(l[a[i]], max(0, i - d));
		r[a[i]] = min(i, r[a[i]]);
	}
	int res = 1;
	for (int i = 1; i <= n; i++){
		ps[i] = ps[i - 1] + C[i];
		if (cnt[i] > 0){
			int kojj = lower_bound(all(koj[i]), l[i]) - koj[i].begin();
			int koj2 = upper_bound(all(koj[i]), r[i]) - koj[i].begin();
			res = res * 1ll * (max(0,koj2 - kojj)) % MOD;
		}else{
			res = res * 1ll * (max(0, ps[i] - i + 1)) % MOD;
		}
	}
	cout << res;
	return 0;
}