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<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=300005;
const int MOD=998244353;
int n,A[N],a[N];
bool vis[N];
int L[N],R[N];
int s[N];//已经确定的位置 
int tim;
int ans=1;
struct qq
{
	int len,id;
}h[N];int cnt=0;
int pos;
bool cmp (qq x,qq y)	{return x.id<y.id;}
int mul (int x,int y)	{return (LL)x*y%MOD;}
void solve ()
{
	for (int u=1;u<=n;u++)
		if (s[u]!=0)
		{
			pos=u;
			break;
		}
//	printf("ans:%d\n",ans);
/*	printf("%d\n",pos);
	for (int u=1;u<=n;u++) printf("%d ",s[u]);
	printf("\n");*/
	int now=pos,lst=s[now],o=0;
	do
	{
		now++;
		if (now>n) now=1;
		if (s[now]!=0)
		{
			//printf("OZY:%d %d\n",lst,s[now]);
			if (o!=0)
			{
				cnt++;
				h[cnt].len=o;
				h[cnt].id=max(lst,s[now]);
			}	
			lst=s[now];
			o=0;
		}
		else o++;
	}while (now!=pos);
	sort(h+1,h+1+cnt,cmp);
	//for (int u=1;u<=cnt;u++) printf("%d %d\n",h[u].id,h[u].len);
	int lalal=0;
	now=0;
	for (int u=1;u<=n;u++)//这个数需要被插入 
		if (vis[u]==false)
		{
			while (now<=cnt&&h[now+1].id<u)
			{
				now++;
				lalal=lalal+h[now].len;
			}
			//printf("%d %d %d %d\n",u,lalal,now,h[now+1].id);
			if (lalal==0)
			{
				printf("0\n");
				return ;
			}
			ans=mul(ans,lalal);
			lalal--;
		}
	printf("%d\n",ans);
}
int main()
{
	memset(s,0,sizeof(s));
	memset(vis,false,sizeof(vis));
	scanf("%d",&n);
	pos=-1;
	for (int u=0;u<n;u++) 	
	{
		scanf("%d",&A[u]);
		if (pos==-1&&A[u]==1) pos=u;
	}
	if (pos==-1)	{printf("0\n");return 0;}
	if (pos==0)
	{
		for (int u=n-1;u>=0;u--)
			if (A[u]==1)	pos=u;
			else break;
	}
	//printf("%d\n",pos);
	for (int u=1;u<=n;u++) a[u]=A[(pos+u-1)%n];
	/*for (int u=1;u<=n;u++) printf("%d ",a[u]);
	printf("\n");*/
	for (int u=1;u<=n;u++)
	{
		tim=tim+(a[u]==1);
		if (a[u]!=a[u-1])
		{
			if (vis[a[u]]==true)	{printf("0\n");return 0;}
			vis[a[u]]=true;
		}
	}
	//printf("%d\n",tim);
	for (int u=1;u<=n;u++)	
		if (a[u]==a[u-1]) L[u]=L[u-1];
		else L[u]=u;
	for (int u=n;u>=1;u--)
		if (a[u]==a[u+1]) R[u]=R[u+1];
		else R[u]=u;
	//for (int u=1;u<=n;u++) printf("%d %d\n",L[u],R[u]);
	for (int u=1;u<=n;u++)
		if (u==L[u])
		{
			if (R[u]-L[u]+1>tim)
			{
				printf("0\n");
				return 0;
			}
			int pos=-1,pos1=-1;
			int l,r;
			l=L[u]-1;if (l<=0) l+=n; 
			r=R[u]+1;if (r>n) r-=n;
			if (a[l]>a[u])	pos=L[u]+tim-1;
			if (pos>n) pos=pos-n;
			if (a[r]>a[u])  pos1=R[u];
		/*	printf("%d %d\n",L[u],tim);*/
			//printf("YES:%d %d %d %d %d\n",u,l,r,pos,pos1);
			if (pos!=-1&&pos1!=-1&&pos!=pos1)	{printf("0\n");return 0;}
			if (pos!=-1)
			{
				//printf("YES\n");
				if (s[pos]!=0) {printf("0\n");return 0;}
				s[pos]=a[u];
			}
			else if (pos1!=-1)
			{
				if (s[pos1]!=0)	{printf("0\n");return 0;}
				s[pos1]=a[u];
			}
			if (pos==-1&&pos1==-1)
			{
				if (tim<(R[u]-L[u]+1)) {printf("0\n");return 0;}
				//printf("YES:%d\n",a[u]);
				if (L[u]==1&&R[u]==n)	ans=mul(ans,n);
				else 
				{
					int t=tim-(R[u]-L[u]+1)+1;
					//printf("%d %d %d\n",u,t);
					ans=mul(ans,t);
				}
				//printf("%d\n",R[u]);
				s[R[u]]=a[u];
			}
		}
	/*printf("%d\n",ans);
	for (int u=1;u<=n;u++) printf("%d ",s[u]);
	printf("\n");*/
	solve();
	return 0;
}