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 syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=998244353;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

class Union_Find_Tree{
	public:
	vi p,r,s;
	Union_Find_Tree(int n){
		p=r=vi(n);
		s=vi(n,1);
		for(int i=0;i<n;i++) p[i]=i;
	}
	int Par(int x){
		if(p[x]==x) return x;
		return p[x]=Par(p[x]);
	}
	int Size(int x){return s[Par(x)];}
	bool Unite(int x,int y){
		x=Par(x);
		y=Par(y);
		if(x==y) return 0;
		if(r[x]<r[y]){
			p[x]=y;
			s[y]+=s[x];
		}
		else{
			p[y]=x;
			s[x]+=s[y];
			if(r[x]==r[y]) r[x]++;
		}
		return 1;
	}
	bool Same(int x,int y){return Par(x)==Par(y);}
};

int n;
vi a;

int main(){
	cin>>n;
	a=vi(n);
	deque<int> q(n);
	bool B=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i]--;q[i]=a[i];
		if(!a[i]) B=1;
	}
	if(a==vi(n,0)){
		ll res=1;
		for(ll i=1;i<=n;i++) (res*=i)%=mod;
		cout<<res<<endl;
		return 0;
	}
	if(!B){
		cout<<0<<endl;
		return 0;
	}
	while(q[0]!=0||q[n-1]==0){
		int tmp=q[n-1];
		q.push_front(tmp);
		q.pop_back();
	}
	for(int i=0;i<n;i++) a[i]=q[i];
	vi L,R;
	L=R=vi(n,-1);
	ll t=-1;
	for(int i=0;i<n;i++){
		int A=a[i];
		if(t!=A&&L[A]!=-1){
			cout<<0<<endl;
			return 0;
		}
		if(L[A]==-1){
			if(t!=-1) R[t]=i-1;
			t=A;L[A]=i;
		}
	}
	R[t]=n-1;
	ll k=R[0]-L[0],res=1;t=0;
	int N=0;
	vi c(n);
	Union_Find_Tree uft(n);
	for(int i=0;i<n;i++){
		if(L[i]==-1){
			(res*=max(0ll,t-i))%=mod;
			continue;
		}
		int K=R[i]-L[i];
		if(K>k) res=0;
		c[L[i]]=1;
		for(int j=L[i];j<R[i];j++){
			uft.Unite(j,j+1);
			c[j]=c[j+1]=1;
		}
		N+=K+1;
		int flag=0;
		if(L[i]-1>=0&&c[L[i]-1]){
			t-=uft.Size(L[i]-1)-k;
			uft.Unite(L[i]-1,L[i]);
			flag++;
		}
		if(c[(R[i]+1)%n]){
			t-=uft.Size((R[i]+1)%n)-k;
			uft.Unite(R[i],(R[i]+1)%n);
			flag++;
		}
		if(flag==2) (res*=k-K+1)%=mod;
		if(!flag&&k!=K) res=0; 
		t+=uft.Size(L[i])-k;
		if(N==n) t=n;
	}
	cout<<res<<endl;
}