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>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

void claim(int x){
	if(!x) puts("0"),exit(0);
}

const int N=300005,mod=998244353;
int a[N],b[N],c[N],l[N],r[N],vis[N];
int n,p,len,ans=1,rem;

int main(){
	read(n);
	rep(i,1,n){
		read(a[i]);
		if(!p&&a[i]==1) p=i;
	}
	if(a[n]==1){
		p=n;
		while(a[p-1]==1) p--;
	}
	claim(p);
	rep(i,1,p-1) b[i]=a[i];
	rep(i,1,n-p+1) a[i]=a[i+p-1];
	rep(i,1,p-1) a[i+n-p+1]=b[i];
	/*
	puts("===");
	rep(i,1,n) printf("%d ",a[i]);
	puts("\n---");
	*/
	rep(i,1,n){
		c[a[i]]++;
		if(!l[a[i]]) l[a[i]]=i;
		r[a[i]]=i;
	}
	rep(i,1,n) claim(!c[i]||c[i]==r[i]-l[i]+1&&c[i]<=c[1]);
	len=c[1];
	if(len==n){
		int ans=1;
		rep(i,1,n) ans=(ll)ans*i%mod;
		cout<<ans<<endl;
		return 0;
	}
	rep(i,2,n){
		if(!c[i]){
			claim(rem);
			ans=(ll)ans*(rem--)%mod;
			continue;
		}
		int L=(a[l[i]-1]<i),R=(a[r[i]+1]<i);
		if(L&&R){
			ans=(ll)ans*(len-c[i]+1)%mod;
			rem+=c[i]+len-2;
		}
		else if(L||R) rem+=c[i]-1;
		else claim(c[i]==len);
	}
	cout<<ans<<endl;
	return 0;
}