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<map>
#include<algorithm>
using namespace std;
typedef long long ll;
struct tk
{
	ll l,r;
	bool operator<(const tk&y)const{return r<y.r||(r==y.r&&l<y.l);}
}h;
ll rev,n,i,x[300005],j,seq[300005],tot=0,y[300005],p,fac[300005],invfac[300005],cnt=0,l[300005],r[300005],vis[300005],pos,ans;
const ll mod=998244353;
map<tk,ll> mp;
map<tk,ll>::iterator it;
ll pow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int main()
{
	scanf("%lld",&n);
	fac[0]=ans=1;
	for(i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	invfac[n]=pow(fac[n],mod-2);
	for(i=n-1;i>=0;i--)invfac[i]=invfac[i+1]*(i+1)%mod;
	for(i=1;i<=n;i++)scanf("%lld",&x[i]);
	for(i=1;i<=n;i++)if(x[i]>1)break;
	if(i>n)
	{
		printf("%lld",fac[n]);
		return 0;
	}
	x[0]=x[n];
	for(i=1;i<=n;i++)
	{
		if(x[i]!=x[i-1])
		{
			vis[x[i]]++;
			if(x[i]==1)l[x[i]]=i;
		}
		if(x[i]==1)cnt++;
		if(vis[x[i]]>1)
		{
			printf("0\n");
			return 0;
		}
	}
	mp[(tk){1,n-1}]=1;
	j=1;pos=(l[1]==n)?1:l[1]+1;
	p=cnt-1;
	while(j<n)
	{
		y[j++]=x[pos];
		pos=(pos==n)?1:pos+1;
	}
	cnt=0;
	for(i=1;i<=n;i++)
	{
		if(!l[y[i]])l[y[i]]=i;
		r[y[i]]=i;
	}
	for(i=2;i<=n;i++)
	{
		if(!l[i])seq[++tot]=cnt;
		else
		{
			it=mp.lower_bound((tk){-1,r[i]});
			h=it->first;
			if(r[i]-l[i]+1>p+1)
			{
				printf("0\n");
				return 0;
			}
			if(l[i]>h.l+p)
			{
				mp.erase(h);
				mp[(tk){h.l,l[i]-1}]=1;
				if(r[i]<h.r)
				{
					if(r[i]-l[i]+1!=p+1)
					{
						printf("0\n");
						return 0;
					}
					mp[(tk){l[i]+1,h.r}]=1;
				} 
				else cnt+=h.r-l[i];				
			}
			else
			{
				if(r[i]<h.r)
				{
					cnt+=r[i]-p-h.l;
					mp.erase(h);
					mp[(tk){r[i]-p+1,h.r}]=1;
				}
				else
				{
					ans=ans*(p+1-r[i]+l[i])%mod;
					cnt+=h.r-h.l;
					mp.erase(h);
				}
			}
		}
	}
	for(i=1;i<=tot;i++)
	{
		if(seq[i]-i+1>0)ans=ans*(seq[i]-i+1)%mod;
		else
		{
			printf("0\n");
			return 0;
		}
	}
	printf("%lld\n",ans);
	return 0;
}