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;

#define LL long long
#define N 800000

const LL mod=998244353;
LL n,len,vis[N],a[N],ans,sum,num[N],q[N],cnt[N];

void all_1(){
	LL tmp=1;
	for (LL i=1;i<=n;++i){
		if (a[i]!=1) return;
		tmp=tmp*i%mod;
	}
	printf("%lld\n",tmp); exit(0);
}

void no_1(){
	bool fl=1;
	for (LL i=1;i<=n;++i) if (a[i]==1){fl=0; break;}
	if (fl){puts("0"); exit(0);}
}

void too_long(){
	for (LL i=2,j=1;i<=n;++i){
		if (a[i]==a[i-1]) ++j;
		else j=1;
		if (j>len){puts("0"); exit(0);}
	}
}

void not_continue(){
	vis[1]=1;
	for (LL i=2;i<=n;++i){
		if (a[i]!=a[i-1]&&vis[a[i]]){puts("0"); exit(0);}
		vis[a[i]]=1;
	}
	memset(vis,0,sizeof vis);
}

int main(){
	scanf("%lld",&n);
	for (LL i=1;i<=n;++i) scanf("%lld",a+i);
	all_1(); no_1();
	for (LL i=1;i<=n;++i) a[i+n]=a[i];
	for (LL i=2;i<=n+1;++i)
		if (a[i]==1&&a[i-1]!=1){
			for (LL j=1;j<=n;++j) a[j]=a[j+i-1];
			break;
		}
	a[n+1]=0;
	for (len=1;len<=n;++len) if (a[len+1]!=1) break;
	for (LL i=n,tt=1,ww=0;i;--i){
		for (;tt<=ww&&q[tt]>=i+len;++tt);
		for (;tt<=ww&&a[q[ww]]<a[i];--ww);
		q[++ww]=i;
		++cnt[a[q[tt]]];
	}
	too_long(); not_continue();
	for (LL i=len+1;i<=n;++i){
		if (a[i]>a[i-1]){
			LL x=a[i-1];
			if (vis[x]&&vis[x]!=i-len){puts("0"); return 0;}
			vis[x]=i-len;
			num[x]=1;
		}
		if (a[i]<a[i-1]){
			LL x=a[i];
			if (vis[x]&&vis[x]!=i){puts("0"); return 0;}
			vis[x]=i;
			num[x]=1;
		}
	}
	for (LL i=2;i<=n;++i)
		if (a[i]>a[i-1]&&!vis[a[i]]){
			vis[a[i]]=1;
			for (LL j=i;a[j]==a[i];++j) ++num[a[i]];
			num[a[i]]=len-num[a[i]]+1;
			for (LL j=i-1;j>=i-num[a[i]]+1;--j)
				if (a[j]>a[i]){puts("0"); return 0;}
		}
	ans=1;
	for (LL i=1;i<=n;++i){
		sum+=cnt[i];
		if (vis[i]) ans=ans*num[i]%mod;
		else ans=ans*sum%mod;
		--sum;
	}
	printf("%lld\n",ans);
	
	return 0;
}