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 fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 666666, mo = 998244353;
int n,a[N],b[N],cnt[N],res=1;
void GG(){puts("0");exit(0);}
Pii seg[N];

/*int lzy[N<<1],val[N<<1];
void update(int k){val[k]=val[k<<1]+val[k<<1|1];}
void pushdown(int k,int l,int r){
	if(lzy[k]){
		lzy[k<<1]=lzy[k<<1|1]=1;lzy[k]=0;
		int mid=(l+r)>>1;
		val[k<<1]=mid-l+1;val[k<<1|1]=r-mid;
	}
}
void cover(int k, int l, int r, int L, int R){
	if(r<L||l>R)return;
	if(l<=L&&r>=R){lzy[k]=1;val[k]=R-L+1;return;}
	int mid=(L+R)>>1;pushdown(k,L,R);
	cover(k<<1,l,r,L,mid);cover(k<<1|1,l,r,mid+1,R);update(k);
}
int query(int k,int l,int r, int L, int R){
	if(r<L||l>R)return 0;
	if(l<=L&&r>=R)return val[k];
	pushdown(k,L,R);int mid=(L+R)>>1;
	return query(k<<1,l,r,L,mid)+query(k<<1|1,l,r,mid+1,R);
}
void shrink(int &l, int &r){
	per(i,18,0)if(l+(1<<i)<=r&&query(1,l,l+(1<<i)-1,1,n)==(1<<i))l+=1<<i;
	per(i,18,0)if(r-(1<<i)>=l&&query(1,r-(1<<i)+1,r,1,n)==(1<<i))r-=1<<i;
}*/
bool c[N];
inline void cover(int l, int r){rep(i,l,r)c[i]=1;}
inline void shrink(int &l, int &r){
	if(c[l])per(i,18,0)if(l+(1<<i)-1<=r&&c[l+(1<<i)-1])l+=1<<i;
	if(c[r])per(i,18,0)if(r-(1<<i)+1>=l&&c[r-(1<<i)+1])r-=1<<i;
}
int main() {
	read(n);rep(i,1,n)read(a[i]);
	rep(s,1,n)if(a[s]==1&&a[s-1>=1?s-1:n]!=1){//WA
		for(int i=1;i<=n;i++)b[i]=a[s+i-1<=n?s+i-1:s+i-1-n];
		memcpy(a,b,sizeof(b));break;
	}
	if(a[1]!=1)GG();
	rep(i,1,n){
		int j;for(j=i;j<=n;j++)if(a[j]!=a[i])break;
		seg[a[i]]=Pii(i,j-1);//printf("G %d\n",a[i]);
		if(cnt[a[i]])GG();cnt[a[i]]=1;i=j-1;
	}
	int x;for(x=1;x<=n;x++)if(a[x]!=1)break;x--;
//	printf("x = %d\n",x);
	int now=1;for(int i=n;i>=2;i--,now++)if(seg[i].fi){//WA
		int l=seg[i].fi-x+1,r=seg[i].se,L=seg[i].se-x+1,R=seg[i].fi;
		shrink(l,r);shrink(L,R);
	//	printf("%d : %d %d %d %d\n",i,l,r,L,R);
		if(L>R)GG();res=1LL*res*(R-L+1)%mo;now--;
		rep(t,l,r-1)res=1LL*res*now%mo,now--;
		cover(l,r);
	}
	if(a[n]==1){res=1;rep(i,1,n)res=1LL*res*i%mo;cout<<res;return 0;}//TEPAN
	rep(i,1,now)res=1LL*res*i%mo;cout<<res;
	return 0;
}