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<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int a[300100];
int mi[300100],le[300100];
int rm[300100];
vector<int> num,len;
vector<pint> p;
vector<int> v;
vector<lint> zyo,rz;
lint mo=998244353;
lint extgcd(lint a, lint b, lint &x, lint &y) {
  lint g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
lint invMod(lint a, lint m) {
  lint x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;return 0;
}
lint calp(int a,int b){
	//cout<<a<<' '<<b<<endl;
	if(a<b) return 0;
	return (zyo[a]*rz[a-b])%mo;
}
int main()
{
	zyo.pb(1);rep(i,300200) zyo.pb((zyo[i]*(i+1))%mo);
	rep(i,300200) rz.pb(invMod(zyo[i],mo));
	
	int n;
	cin>>n;
	rep(i,n){
		cin>>a[i];a[i]--;
	}
	rep(i,n) mi[i]=n+10;
	rep(i,n) mi[a[i]]=min(mi[a[i]],i);
	rep(i,n){
		if(mi[i]!=0) continue;
		int t=n-1;
		while(t>=0 && a[t]==i) t--;
		mi[i]=(t+1)%n;
	}
	rep(i,n){
		rm[mi[i]]=i;
		le[i]=0;
		if(mi[i]>n){
			continue;
		}
		while(le[i]<n && a[(mi[i]+le[i])%n]==i) le[i]++;
	}
	
	//rep(i,n) cout<<mi[i]<<' '<<le[i]<<endl;
	//rep(i,n) mi[i]+le[i];
	
	int sl=0;
	rep(i,n) sl+=le[i];
	if(sl!=n){
		cout<<0<<endl;return 0;
	}
	if(mi[0]>n){
		cout<<0<<endl;return 0;
	}
	if(le[0]==n){
		cout<<zyo[n]<<endl;return 0;
	}
	int now=0;
	while(1){
		num.pb(now);len.pb(le[now]);
		now=rm[(mi[now]+le[now])%n];
		if(now==0) break;
	}
	int m=num.size();lint out=1;
	//rep(i,m) cout<<num[i]<<' '<<len[i]<<endl;
	REP(i,1,m){
		if(num[i]>0 && len[i]>len[0]){
			cout<<0<<endl;return 0;
		}
		if(len[i]<len[0]){
			if(num[i]<num[i-1] && i<m-1 && num[i]<num[i+1]){
				cout<<0<<endl;return 0;
			}
			else if(num[i]>num[i-1] && (i>=m-1 || num[i]>num[i+1])){
				out*=len[0]-len[i]+1;out%=mo;
			}
		}
	}
	int tu=len[0];
	rep(i,m-1){
		if(len[i+1]<tu){
			if(num[i+1]>num[i]) len[i]=len[i+1],len[i+1]=tu;
			//if(num[i+1]>num[i] && (i>=m-2 || num[i+1]>num[i+2]))
		}
	}
	rep(i,m){
		int bo=num[i];
		if(i<m-1) bo=max(bo,num[i+1]);
		p.pb(mp(bo,len[i]-1));
		v.pb(num[i]);
	}
	sort(All(p));reverse(All(p));
	sort(All(v));reverse(All(v));
	//rep(i,m) cout<<p[i].fi<<' '<<p[i].se<<endl;
	int used=0,i1=0,i2=0;
	while(i1<m){
		while(i2<m && v[i2]>p[i1].fi){
			i2++;used++;
		}
		out*=calp(n-p[i1].fi-used-1,p[i1].se);
		out%=mo;
		used+=p[i1].se;
		i1++;
	}
	cout<<out<<endl;
}