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;
const int sz=6e5+7;
const int mod=998244353;
int n,t;
int ans;
int cnt;
int pos;
int sum;
bool flag;
int a[sz];
int fac[sz];
int st[sz],ed[sz];
int main(){
	scanf("%d",&n);
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*i*fac[i-1]%mod;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[n+i]=a[i];
	}
	pos=2;
	while(a[pos]==a[pos-1]) ++pos;
	if(pos==2*n+1&&a[1]!=1) return printf("0\n"),0;
	if(pos==2*n+1) return printf("%d\n",fac[n]),0;
	for(int i=pos;i<pos+n;i++){
		if(a[i]!=a[i-1]){
			if(st[a[i]]) flag=1;
			st[a[i]]=i;
		}
		if(a[i]!=a[i+1]) ed[a[i]]=i;
	}
	if(flag) return printf("0\n"),0;
	
	t=ed[1]-st[1];
	for(int i=1;i<=n;i++) if(ed[i]-st[i]>t) flag=1;
	if(flag) return printf("0\n"),0;
	
	ans=1;
	cnt=1,sum=t+1;
	for(int i=2;i<=n;i++){
		if(!st[i]) { ans=1ll*(sum-t*cnt-i+1)*ans%mod;continue; }
		int k1=a[st[i]-1]<i,k2=a[ed[i]+1]<i;
		if(k1&&k2) ans=1ll*(st[i]-(ed[i]-t)+1)*ans%mod,cnt--;
		if(!k1&&!k2) cnt++;
		if(!k1&&!k2&&ed[i]-st[i]!=t) ans=0;
		sum+=ed[i]-st[i]+1;
	}
	printf("%d\n",ans);
}