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<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-9;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int p[310000];
int u[310000];
int d[310000];
int ev[310000];
int ind[310000];
int val[310000];
int segtree[1048576];
int z[310000];
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 0;
	if(c<=a&&b<=d)return segtree[e];
	return max(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
void update(int a,int b){
	a+=524288;
	while(a){
		segtree[a]=max(segtree[a],b);
		a/=2;
	}
}
int calc(int a,int b){
	if(a>b)return max(calc(0,b),calc(a,524287));
	return query(0,524287,a,b,1);
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);p[i]--;
	}
	int st=-1;
	int now=0;
	int sl=0;
	int len=0;
	for(int i=0;i<2*a;i++){
		if(p[i%a]==0){
			if(now==0)st=i;
			now++;
			if(len<now){
				len=now;sl=st;
			}
		}else{
			now=0;
		}
	}
	if(len==0){
		printf("0\n");return 0;
	}
	for(int i=len;i<a;i++){
		if(p[(i+sl)%a]==0){
			printf("0\n");return 0;
		}
	}
	for(int i=0;i<a;i++)d[i]=-1;

	for(int i=len;i<a;i++){
		if(p[(i+sl)%a]<p[(i+sl+1)%a]){
			d[(i+sl-len+1)%a]=p[(i+sl)%a];
		}
		if(p[(i+sl)%a]>p[(i+sl+1)%a]){
			d[(i+sl+1)%a]=p[(i+sl+1)%a];
		}
	}

	long long ret=1;
	int sz=0;
	for(int i=0;i<a;i++){

		if(i==0||p[(i+sl)%a]!=p[(i+sl+a-1)%a]){
			ind[sz]=i;
			val[sz++]=p[(i+sl)%a];
		}
	}
	//for(int i=0;i<sz;i++)printf("%d %d\n",ind[i],val[i]);
	for(int i=0;i<sz;i++){
		if((ind[(i+1)%sz]+a-ind[i])%a>len){
			ret=0;
		}
		if(val[i]>val[(i+1)%sz]&&val[i]>val[(i+sz-1)%sz]){
			d[(ind[i]+sl)%a]=val[i];
			int L=(ind[(i+1)%sz]+a-ind[i])%a;
			ret=(ret*(max(0,len-L+1)))%mod;
		}
	}
	int f=0;
	for(int i=0;i<a;i++){
		if(~d[i]){
			u[d[i]]++;
			
		}
	}
	for(int i=0;i<a;i++){
		if(u[i]>1){
			printf("0\n");return 0;
		}
		if(u[i]==0){
			z[f++]=i;
		}
	}
//	for(int i=0;i<a;i++){
//		printf("%d ",d[i]);
//	}printf("\n");
	int rem=a;
	int n=0;
	for(int i=0;i<a;i++)
		update(i,p[i]);
	
	for(int i=0;i<a;i++){
		if(~d[i]){
//			printf("%d %d %d\n",i,d[i],calc(i,(i+len-1)%a));
			if(calc(i,(i+len-1)%a)>d[i]){ret=0;break;}
			continue;
		}
		ev[n++]=lower_bound(z,z+f,calc(i,(i+len-1)%a))-z;
	}
	if(ret==0){
		printf("0\n");return 0;
	}
	std::sort(ev,ev+n);
//	for(int i=0;i<n;i++){
//		printf("%d ",ev[i]);
//	}printf("\n");
	for(int i=n-1;i>=0;i--){
		ret=ret*max(0,(f-ev[i])-(n-i-1))%mod;
	}
	printf("%lld\n",ret);
}
/*
1 1 2
1   

3 5 6 7 8
0 0 1 1 1
*/