#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=6e5+10,inf=0x3f3f3f3f,mod=998244353;
struct Segment_tree{
	int Min[maxn<<2];
	void update(int x,int L,int R,int ql,int qr,int v){
		if(ql<=L && R<=qr){
			chkmax(Min[x],v);
			return;
		}
		int Mid=(L+R)>>1;
		if(ql<=Mid) update(x<<1,L,Mid,ql,qr,v);
		if(qr>Mid) update(x<<1|1,Mid+1,R,ql,qr,v);
	}
	int query(int x,int L,int R,int q){
		if(L==R) return Min[x];
		int Mid=(L+R)>>1,res=Min[x];
		if(q<=Mid) chkmax(res,query(x<<1,L,Mid,q));
		else chkmax(res,query(x<<1|1,Mid+1,R,q));
		return res;
	}
}Seg;
int n,a[maxn<<1],sum[maxn],Max[maxn];
struct szsz{
	int c[maxn];
	inline int lowbit(int x){
		return x&(-x);
	}
	int sum(int x){
		int res=0;
		while(x){
			res+=c[x];
			x-=lowbit(x);
		}
		return res;
	}
	void add(int x,int y){
		while(x<=n){
			c[x]+=y;
			x+=lowbit(x);
		}
	}
	int query(int l,int r){
		if(l<=0) l+=n;
		if(r>n) r-=n;
		if(l<=r) return sum(r)-sum(l-1);
		return sum(r)+sum(n)-sum(l-1);
	}
}bit;
int l[maxn],r[maxn],tmp;
int L[maxn],R[maxn];
vector<int> ve[maxn];
int main(){
	n=read();
	REP(i,1,n) a[i]=read(),sum[a[i]]++,a[i+n]=a[i];
	int Nw=1,lst=1;
	REP(i,2,n<<1|1)
		if(a[i]!=a[i-1]) l[++tmp]=lst,r[tmp]=i-1,chkmax(Max[a[i-1]],Nw),Nw=1,lst=i;
		else ++Nw;
	REP(i,1,n) if(Max[i]<sum[i]) return printf("0\n"),0;
	if(sum[1]==0) return printf("0\n"),0;
	int Times=sum[1]-1;
	if(Times==n-1){
		int fac=1;
		REP(i,1,n) fac=(ll)fac*i%mod;
		return printf("%d\n",fac),0;
	}
	REP(i,2,tmp){
		if(r[i]-Times>l[i]) return printf("0\n"),0;
		L[a[r[i]]]=r[i]-Times,R[a[r[i]]]=l[i];
		int u=l[i]-Times,v=r[i];
		if(v>n) v-=n;
		if(u<=0) u+=n;
		if(u<=v) Seg.update(1,1,n,u,v,a[r[i]]);
		else Seg.update(1,1,n,u,n,a[r[i]]),Seg.update(1,1,n,1,v,a[r[i]]);
		if(r[i]>n) break;
	}
	REP(i,1,n) ve[Seg.query(1,1,n,i)].push_back(i);
	int ans=1;
	REP(i,1,n){
		for(auto v:ve[i]) bit.add(v,1);
		if(R[i]){
			int u=bit.query(L[i],R[i]);
			if(u==0) return printf("0\n"),0;
			ans=(ll)ans*u%mod;
		}
		else{
			int u=bit.sum(n);
			if(u<i) return printf("0\n"),0;
			ans=(ll)ans*(u-(i-1))%mod;
		}
	}
	assert(bit.sum(n)==n);
	printf("%d\n",ans);
	return 0;
}
