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;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb insert
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSR(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n;
int a[300005];
vector<int>pos[300005];
ll ans = 1;
int main(){
	scanf("%d",&n);
	rep(i,n){
		scanf("%d",&a[i]);
		a[i]--;
		pos[a[i]].push_back(i);
	}
	rep(i,n) SORT(pos[i]);
	int a = pos[0].size();
	if(a == 0){
		puts("0") ; return 0;
	}
	if(a == n){
		repn(i,n) ans = ans*1LL*i%mod;
		cout << ans << endl; return 0;
	}
	vector<int>vec;
	for(int i=1;i<pos[0].size();i++){
		vec.push_back(pos[0][i]-pos[0][i-1]);
	}
	int sum = 0,cnt = 0,beg = pos[0][0];
	rep(i,vec.size()){
		if(vec[i] != 1){
			cnt++;
			beg = pos[0][i+1];
		}
		sum += vec[i];
	}
	if(cnt >= 2 && (cnt == 1 && sum != n-1)){
		puts("0") ; return 0;
	}
	int zan = 0;
	set<P>S;
	int lb = (beg+a)%n;
	int ub = (beg+n-1)%n;
	if(lb > ub) ub += n;
	S.pb(mp(lb,ub));
	int X = lb, Y = ub;
	for(int i=1;i<n;i++){
		if(pos[i].empty()){
			if(zan == 0){
				puts("0"); return 0;
			}
			ans = ans*1LL*zan%mod;
			zan --;
			continue;
		}
		if(pos[i].size() > a){
			puts("0"); return 0;
		}
		vector<int>vec;
		for(int ii=1;ii<pos[i].size();ii++){
			vec.push_back(pos[i][ii]-pos[i][ii-1]);
		}
		int sum = 0,cnt = 0,beg = pos[i][0];
		rep(ii,vec.size()){
			if(vec[ii] != 1){
				cnt++;
				beg = pos[i][ii+1];
			}
			sum += vec[ii];
		}
		if(cnt >= 2 && (cnt == 1 && sum != n-1)){
			puts("0") ; return 0;
		}
		int L = beg;
		int R = (beg+pos[i].size()-1)%n;
		if(L > R) R+=n;
		if(R<X){
			L+=n; R+=n;
		}
		if(Y<L){
		    L-=n; R-=n;
		}
		vector<P>cand;
		set<P>::iterator it = S.lower_bound(mp(L,R));
		if(it != S.end()){
			cand.push_back(*it);
			it++;
			if(it != S.end()){
				cand.push_back(*it);
			}
			it--;
		}
		if(it != S.begin()){
			it--;
			cand.push_back(*it);
			it++;
		}
		rep(x,cand.size()) S.erase(S.find(cand[x]));
		int C = 0;
		rep(x,cand.size()){
			int mn = min(cand[x].sc,R);
			int mx = max(cand[x].fi,L);
			if(mn-mx+1 <= 0){
				S.insert(cand[x]); continue;
			}
			else{
				C++;
				if(cand[x].fi <= L && R <= cand[x].sc){
					if(cand[x].fi == L && cand[x].sc == R){
					    int mnn = L-a+1,mxx = R;
						ans = ans*1LL*(a-(R-L))%mod;
						zan += (mxx-mnn);
					}
					else if(cand[x].fi == L){
						zan += R-cand[x].fi;
						S.insert(mp(R+1,cand[x].sc));
					}
					else if(cand[x].sc == R){
						zan += cand[x].sc-L;
						S.insert(mp(cand[x].fi,L-1));
					}
					else{
						if(R-L+1 != a){
							puts("0") ; return 0;
						}
						S.insert(mp(cand[x].fi,L-1));
						S.insert(mp(R+1,cand[x].sc));
					}
				}
				else{
					puts("0") ; return 0;
				}
			}
		}
	/*	if(S.size() == 0){
		    int zan = n-1-i;
		    for(int i=1;i<=zan;i++) ans = ans*1LL*i%mod;
		    cout << ans << endl;
		    return 0;
		}*/
		//assert(C == 1);
	}
	cout << ans << endl;
}