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
const ll Mod=998244353;
int n,a[300010],b[300010],len,v[300010],q[600010],s[300010];
ll ans;
bool used[300010];
void add(int x,int y)
{
	s[v[x]]+=y;
}
int main()
{
	scanf("%d",&n);
	for (int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	int t=0;
	for (int i=1;i<n;i++)
	{
		if (a[i]==1 && a[i-1]!=1)
		{
			t=i;
		}
	}
	for (int i=0;i<n;i++)
	{
		b[i]=a[(t+i)%n];
	}
	for (int i=0;i<n;i++)
	{
		a[i]=b[i];
		//cerr<<a[i]<<" ";
	}
	//cerr<<endl;
	len=0;
	while (len<n && a[len]==1)
	{
		len++;
	}
	if (!len)
	{
		puts("0");
		return 0;
	}
	if (len==n)
	{
		ans=1;
		for (int i=2;i<=n;i++)
		{
			ans=ans*i%Mod;
		}
		cout<<ans<<endl;
		return 0;
	}
	used[1]=true;
	for (int i=1;i<n;i++)
	{
		if (a[i]==a[i-1])
		{
			continue;
		}
		if (used[a[i]])
		{
			puts("0");
			return 0;
		}
		int j=i;
		while (j<n && a[j]==a[i])
		{
			j++;
		}
		if (j-i>len)
		{
			puts("0");
			return 0;
		}
		used[a[i]]=true;
		i=j-1;
	}
	ans=1;
	int l=1,r=0;
	for (int i=1;i<len;i++)
	{
		while (l<=r && a[q[r]]<=a[i])
		{
			r--;
		}
		q[++r]=i;
	}
	v[0]=1;
	for (int i=1;i<n;i++)
	{
		while (l<=r && a[q[r]]<=a[(i+len-1)%n])
		{
			r--;
		}
		q[++r]=(i+len-1)%n;
		v[i]=a[q[l]];
		if (q[l]==i)
		{
			l++;
		}
	}
	l=0,r=-1;
	for (int i=len;i<n;i++)
	{
		if (a[i]==a[i-1])
		{
			continue;
		}
		int j=i;
		while (j<n && a[j]==a[i])
		{
			j++;
		}
		while (r<i)
		{
			r++;
			add(r,1);
		}
		while (l<j-len)
		{
			add(l,-1);
			l++;
		}
		ans=ans*s[a[i]]%Mod;
		//cerr<<l<<" "<<r<<" "<<s[a[i]]<<endl;
		i=j-1;
	}
	memset(s,0,sizeof(s));
	for (int i=0;i<n;i++)
	{
		s[v[i]]++;
		//cerr<<v[i]<<" ";
	}
	//cerr<<endl;
	for (int i=1;i<=n;i++)
	{
		s[i]+=s[i-1];
	}
	for (int i=2;i<=n;i++)
	{
		if (used[i])
		{
			continue;
		}
		if (s[i]<i-1)
		{
			ans=0;
		}
		ans=ans*(s[i]-i+1)%Mod;
	}
	cout<<ans<<endl;
	return 0;
}
//弹破庄周梦，两翅驾东风，三百座名园、一采一个空。
//——王和卿《醉中天·咏大蝴蝶》