#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<int> fact;
vector<int> ifact;
vector<int> inv;
vector<int> pow2;
const int MOD = 998244353;
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); inv.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	inv.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
	for(int i=1;i<=_n;i++)
	{
		inv[i] = mult(fact[i-1],ifact[i]);
	}
}
	
deque<int> a;
int L[611111];
int R[611111];
const int INF = int(1e9);
int C[611111];
struct Fenwick
{
	vector<int> t;
    Fenwick(int n)
    {
        t.assign(n+1,0);
    }
    void reset(int n)
    {
		t.assign(n+1, 0);
	}
    void update(int p, int v)
    {
		p++;
        for (; p < (int)t.size(); p += (p&(-p))) t[p] += v;
    }
    int query(int r) //finds [1, r] sum
    {        
		r++;             
        int sum = 0;
        for (; r; r -= (r&(-r))) sum += t[r];
        return sum;
    }
    int query(int l, int r) //finds [l, r] sum
    {
		if(l == 0) return query(r);
		return query(r) - query(l-1);
	}
};

int k,n;
int fix(int x)
{
	while(x>=n) x-=n;
	while(x<0) x+=n;
	return x;
}
int cc;
set<ii> S;
/*
void ins(int l, int r)
{
	S.insert(mp(l,r));
	auto it = S.find(mp(l,r));
	cc+=max(0,r-l+1-(k-1));
	while(it!=S.begin())
	{
		int l2=prev(it)->fi; int r2=prev(it)->se;
		if(r2==l-1)
		{
			//cerr<<l<<' '<<r<<' '<<l2<<' '<<r2<<' '<<cc<<'\n';
			cc-=max(0,r2-l2+1-(k-1));
			cc-=max(0,r-l+1-(k-1));
			cc+=max(0,r-l2+1-(k-1));
			S.erase(mp(l2,r2)); S.erase(mp(l,r));
			l=l2;
			it=S.insert(mp(l2,r)).fi;
		}
		else break;
	}
	while(next(it)!=S.end())
	{
		int l2=next(it)->fi; int r2=next(it)->se;
		if(l2==r+1)
		{
			//cerr<<l<<' '<<r<<' '<<l2<<' '<<r2<<'\n';
			cc-=max(0,r2-l2+1-(k-1));
			cc-=max(0,r-l+1-(k-1));
			cc+=max(0,r2-l+1-(k-1));
			S.erase(mp(l2,r2)); S.erase(mp(l,r));
			it=S.insert(mp(l,r2)).fi;
			r=r2;
		}
		else break;
	}
	//cerr<<"INSERT "<<cc<<'\n';
}
*/

struct DSU
{
	int S;
	
	struct node
	{
		int p; int sum;
	};
	vector<node> dsu;
	
	DSU(int n)
	{
		S = n;
		for(int i = 0; i < n; i++)
		{
			node tmp;
			tmp.p = i; tmp.sum = 1;
			dsu.pb(tmp);
		}
	}
	
	void reset(int n)
	{
		dsu.clear();
		S = n;
		for(int i = 0; i < n; i++)
		{
			node tmp;
			tmp.p = i; tmp.sum = 1;
			dsu.pb(tmp);
		}
	}
	
	int rt(int u)
	{
		if(dsu[u].p == u) return u;
		dsu[u].p = rt(dsu[u].p);
		return dsu[u].p;
	}
	
	void merge(int u, int v)
	{
		u = rt(u); v = rt(v);
		if(u == v) return ;
		if(rand()&1) swap(u, v);
		cc -= max(dsu[u].sum - (k-1), 0);
		cc -= max(dsu[v].sum - (k-1), 0);
		dsu[v].p = u;
		dsu[u].sum += dsu[v].sum;
		cc += max(dsu[u].sum - (k-1), 0);
	}
	
	bool sameset(int u, int v)
	{
		if(rt(u) == rt(v)) return true;
		return false;
	}
	
	ll getstat(int u)
	{
		return dsu[rt(u)].sum;
	}
};

map<vi,int> ma;
void gen(int n)
{
	vi perm(n);
	for(int i=0;i<n;i++) perm[i]=i;
	do
	{
		vi V=perm;
		while(1)
		{
			ma[V]++;
			vi W(n);
			for(int i=0;i<n;i++)
			{
				W[i]=min(V[i],V[(i+1)%n]);
			}
			if(V==W) break;
			V=W;
		}
	}while(next_permutation(perm.begin(),perm.end()));
}
const int CC = 102192;
int vis[333333];
int main()
{
	srand(CC);
	ios_base::sync_with_stdio(0); cin.tie(0);
	init(601111);
	cin>>n;
	int cnt=0;
	for(int i=0;i<n;i++) L[i]=INF,R[i]=-INF;
	a.resize(n);
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; 
		a[i]--;
		if(a[i]==0) cnt++;
		//L[a[i]] = min(L[a[i]],i);
		//R[a[i]] = max(R[a[i]],i);
		C[a[i]]++;
	}
	/*
	gen(n);
	vi v;
	for(int i=0;i<n;i++) v.pb(a[i]);
	cout<<"ANS : "<<ma[v]<<'\n';
	*/
	if(cnt==n)
	{
		cout<<fact[n]<<'\n';
		return 0;
	}
	for(int i=1;i<n;i++)
	{
		if(C[i]==n){cout<<0<<'\n'; return 0;}
	}
	while(a[0]==a[n-1])
	{
		int x = a.back(); a.pop_back();
		a.push_front(x);
	}
	for(int i=0;i<n;i++)
	{
		L[a[i]] = min(L[a[i]],i);
		R[a[i]] = max(R[a[i]],i);
	}
	for(int i=0;i<n;i++)
	{
		if(L[i]<INF)
		{
			if(R[i]-L[i]+1!=C[i])
			{
				cout<<0<<'\n'; return 0;
			}
		}
	}
	k = C[0];
	int ans = 1;
	Fenwick fen(n);
	int ct=0;
	/*
	for(int i=0;i<n;i++) cerr<<a[i]<<' ';
	cerr<<'\n';
	*/
	DSU dsu(n);
	for(int i=1;i<n;i++)
	{
		if(C[i-1]>0)
		{
			for(int j=L[i-1];j<=R[i-1];j++)
			{
				vis[j]=1;
				if(vis[fix(j-1)]) dsu.merge(j,fix(j-1));
				if(vis[fix(j+1)]) dsu.merge(j,fix(j+1));
				fen.update(j,1); 
				//ct++;
			}
			//ins(L[i-1],R[i-1]);
			//cerr<<"CC "<<cc<<'\n';
		}
		if(C[i]==k) 
		{
			continue;
		}
		if(C[i]>k)
		{
			cout<<0<<'\n'; return 0;
		}
		int l = L[i]; int r = R[i];
		if(C[i]>0)
		{
			
			int r2=fix(r+1);
			if(!fen.query(r2,r2))
			{
				int l2=fix(l-1);
				if(!fen.query(l2,l2))
				{
					cout<<0<<'\n'; return 0;
				}
				//must start at r - k + 1
				continue;
				//cout<<0<<'\n'; return 0;
			}
			
			int l2=fix(l-1);
			if(!fen.query(l2,l2))
			{
				continue;
			}
			//cerr<<"K : "<<k-(r-l)<<'\n';
			ans = mult(ans,k-(r-l));
		} 
		else
		{
			//cerr<<i<<' '<<cc-i<<'\n';
			if(fen.query(0,n-1)==n) ans=mult(ans,n-i);
			else ans=mult(ans,max(0,cc-i));
		}
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 26864