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,l,r) for (int i=l,i##end=r;i<=i##end;++i)
#define per(i,r,l) for (int i=r,i##end=l;i>=i##end;--i)
#define rep0(i,r) for (int i=0,i##end=r;i<i##end;++i)
#define nosol { printf("0\n"); return 0; }
#define ll long long
using namespace std;
const int N=1e6+6,P=998244353;
int n,s,k,fa[N],sz[N],a[N],lm[N],rm[N],st[N],l[N],r[N];
vector<int> G[N];
int getfa(int u){ return fa[u]==u?u:fa[u]=getfa(fa[u]); }
int calc(int x){ return x==n?n:max(x-(k-1),0); }
void merge(int x,int y){
	x=getfa(x),y=getfa(y); if (x==y) return;
	s+=calc(sz[x]+sz[y])-calc(sz[x])-calc(sz[y]); 
	fa[y]=x,sz[x]+=sz[y];
}
bool check(int x){
	int m=G[x].size(); if (!m) return true;
	if (G[x][0]==1||G[x][m-1]==n){
		int c=0,t=n; while (a[t]==x) ++c,--t; l[x]=t;
		t=1; while (a[t]==x) ++c,++t; r[x]=t;
		return c==m;
	}
	else{
		int c=0,t=G[x][0]; while (a[t]==x) ++c,++t; 
		l[x]=G[x][0]-1,r[x]=t; return c==m;
	}
}
int pre(int i){ return i==1?n:i-1; }
int suc(int i){ return i==n?1:i+1; }
int main(){
	int c1=0; scanf("%d",&n); 
	rep(i,1,n){
		scanf("%d",&a[i]); G[a[n+i]=a[i]].push_back(i);
	}
	if (G[1].size()==n){
		int ans=1; rep(i,2,n) ans=(ll)ans*i%P; 
		printf("%d\n",ans); return 0;
	}
	rep(i,1,n) if (!check(i)) nosol 
	int tp=0;
	rep(i,1,2*n){
		while (tp&&a[st[tp]]<a[i]) --tp;
		lm[i]=st[tp]?st[tp]:-n; st[++tp]=i;	
	}
	tp=0;
	per(i,2*n,1){
		while (tp&&a[st[tp]]<a[i]) --tp;
		rm[i]=st[tp]?st[tp]:3*n; st[++tp]=i;
	}
	int ans=1; k=G[1].size();
	rep(i,1,n) fa[i]=i,sz[i]=0;
	rep(i,1,n){
		int m=G[i].size();
		if (m){	
			if (m>k) nosol
			if (a[l[i]]<i&&a[r[i]]<i) ans=(ll)ans*(k-m+1)%P;
			else if (a[l[i]]>i&&a[r[i]]>i&&m!=k) nosol
		}
		else{
			if (s<i) nosol;
			ans=(ll)ans*(s-i+1)%P;
		}
		rep0(j,m) sz[G[i][j]]=1;
		rep0(j,m){
			int t=G[i][j];
			if (a[pre(t)]<=i) merge(pre(t),t);
			if (a[suc(t)]<i) merge(suc(t),t);
		}
	}
	printf("%d\n",ans);
	return 0;
}