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 <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <cmath>
#include <string>
#include <set>
#include <map>
#include <cassert>
#define SIZE 300005
#define MOD 998244353

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct UF
{
	int par[SIZE],rank[SIZE];
	
	void init(int n)
	{
		for(int i=0;i<n;i++)
		{
			par[i]=i;
			rank[i]=0;
		}
	}
	int find(int x)
	{
		if(par[x]==x) return x;
		return par[x]=find(par[x]);
	}
	void unite(int l,int r)
	{
		par[l]=r;
	}
	bool same(int x,int y)
	{
		return find(x)==find(y);
	}
};
UF left,right;
int A[SIZE];
vector <int> vec[SIZE];
bool use[SIZE];

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
		A[i]--;
		vec[A[i]].push_back(i);
	}
	ll ret=1;
	int cnt=0;
	if(vec[0].size()==n)
	{
		for(int i=1;i<=n;i++) ret=ret*(ll) i%MOD;
		printf("%lld\n",ret);
		return 0;
	}
	int k=vec[0].size();
	left.init(n+2);
	right.init(n+2);
	int zan=n;
	for(int i=0;i<n;i++)
	{
		if(vec[i].empty())
		{
			if(cnt==i)
			{
				ret=0;
				break;
			}
			ret=ret*(ll) (cnt-i)%MOD;
		}
		else
		{
			for(int j=0;j<vec[i].size();j++)
			{
				int v=vec[i][j];
				if(zan>1)
				{
					zan--;
					use[v]=true;
					if(use[(v+1)%n])
					{
						right.unite(v,(v+1)%n);
						left.unite((v+1)%n,v);
					}
					if(use[(v-1+n)%n])
					{
						right.unite((v-1+n)%n,v);
						left.unite(v,(v-1+n)%n);
					}
					int l=left.find(v),r=right.find(v);
					int vl=v-l,vr=r-v;
					if(vl<0) vl+=n;
					if(vr<0) vr+=n;
					cnt-=max(0,vl-k+1);
					cnt-=max(0,vr-k+1);
					cnt+=max(0,vl+vr+1-k+1);
				}
				else
				{
					zan--;
					cnt=n;
				}
			}
			if(zan==0)
			{
				sort(vec[i].begin(),vec[i].end());
				int all=0;
				for(int j=0;j<vec[i].size();j++)
				{
					int v=vec[i][j];
					int u=vec[i][(j+1)%vec[i].size()];
					int L=u-v-1;
					if(L<0) L+=n;
					all+=max(0,L-(n-k)+1);
				}
				ret=ret*(ll) all%MOD;
			}
			else
			{
				bool up=true;
				for(int j=0;j<vec[i].size();j++)
				{
					int v=vec[i][j],u=vec[i][0];
					if(!right.same(v,u))
					{
						up=false;
						break;
					}
				}
				if(!up)
				{
					ret=0;
					break;
				}
				int l=left.find(vec[i][0]),r=right.find(vec[i][0]);
				int L=r-l+1;
				if(L<0) L+=n;
				int vl=L,vr=L;
				for(int j=0;j<vec[i].size();j++)
				{
					int v=vec[i][j];
					int len=v-l;
					if(len<0) len+=n;
					vl=min(vl,len);
					len=r-v;
					if(len<0) len+=n;
					vr=min(vr,len);
				}
				int c=L-vl-vr;
				if(c>k||L<k)
				{
					ret=0;
					break;
				}
				int nm=k-c+1;
				nm=min(nm,vl+1);
				nm=min(nm,vr+1);
				ret=ret*(ll) nm%MOD;
			}
		}
		//printf("%lld : %d\n",ret,cnt);
	}
	printf("%lld\n",ret);
	return 0;
}