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;

template <typename T> void chmin(T&x,const T &y)
{
	if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
	if(x<y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
	char c;
	while(gc<'-');
	if(c=='-')
	{
		int x=gc-'0';
		while(gc>='0')x=x*10+c-'0';
		return -x;
	}
	int x=c-'0';
	while(gc>='0')x=x*10+c-'0';
	return x;
}
#undef gc

const int N=3e5+5,D=998244353;
int a0[N],a[N],mx_suf_k[N],pre_da[N],suf_da[N];
s64 jie[N];
int cnt[N];bool ap[N];

int main()
{
#ifdef kcz
	freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
	int n=read();
	int c1=0,p1=0;
	rep(i,1,n)
	{
		a0[i]=read();
		if(a0[i]==1){++c1;p1=i;}
	}
	jie[0]=1;
	rep(i,1,n)jie[i]=jie[i-1]*i%D;
	if(!c1)
	{
		puts("0");
		exit(0);
	}
	if(c1==n)
	{
		cout<<jie[n];
		exit(0);
	}
	while(a0[p1]==1)p1=(p1==1)?n:p1-1;
	rep(i,1,n)a[i]=a0[p1+i-(p1+i>n?n:0)];
	int k=c1;
	deque<int>q;
	per(i,n,1)
	{
		while(!q.empty()&&a[i]>a[q.back()])q.pop_back();
		q.push_back(i);
		while(q.front()-i>=k)q.pop_front();
		mx_suf_k[i]=a[q.front()];
		++cnt[mx_suf_k[i]];
	}
	rep(i,1,n)
	{
		int j=i-1;
		while(j&&a[j]<=a[i])j=pre_da[j];
		pre_da[i]=j;
	}
	per(i,n,1)
	{
		int j=i+1;
		while(j<=n&&a[j]<=a[i])j=suf_da[j];
		suf_da[i]=j;
	}
	s64 ans=1;
	for(int i=1;i<=n;)
	{
		if(ap[a[i]])
		{
			puts("0");
			exit(0);
		}
		ap[a[i]]=1;
		int j=i;
		while(a[j]==a[i])++j;
		int l=pre_da[i],r=suf_da[i];
		if(r<=n)r-=k;
		r=min(i,r);
		++l;
		l=max(l,j-k);
		if(l>r)
		{
			puts("0");
			exit(0);
		}
		ans=ans*(r-l+1)%D;
		i=j;
	}
	int can=0; 
	rep(i,1,n)
	{
		can+=cnt[i]-ap[i];
		if(!ap[i])ans=ans*(can--)%D;
	} 
	cout<<ans;
}