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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const LL Maxn = 300010;
const LL Mod = 998244353;
LL a[Maxn], n, K;
LL b[Maxn], c[Maxn], cl, pos[Maxn], pi[Maxn], len[Maxn];
bool v[Maxn];
LL jc[Maxn], inv[Maxn];
LL t[Maxn];
LL _max(LL x, LL y) { return x > y ? x : y; }
int main() {
	LL i, j, k;
	scanf("%lld", &n);
	jc[0] = 1;
	for(i = 1; i <= n; i++) jc[i] = jc[i-1]*i%Mod;
	inv[0] = inv[1] = 1;
	for(i = 2; i <= n; i++) inv[i] = inv[Mod%i]*(Mod-Mod/i)%Mod;
	for(i = 2; i <= n; i++) inv[i] = inv[i-1]*inv[i]%Mod;
	for(i = 0; i < n; i++) scanf("%lld", &a[i]);
	for(i = 0; i < n; i++){
		if(a[i] != a[(i+n-1)%n]){
			if(v[a[i]] == true){ printf("0\n"); return 0; }
			v[a[i]] = true;
		}
	}
	for(i = 0; i < n; i++){
		if(a[i] != a[(i+n-1)%n]){
			if(a[i] == 1) break;
		}
	}
	for(j = 0; j < n; j++) b[j] = a[(i+j)%n];
	K = 0;
	while(b[K] == 1) K++;
	if(K == n){ printf("%lld\n", jc[n]); return 0; }
	c[++cl] = 1; pi[cl] = 0;
	t[1] = 1;
	for(i = K; i < n; i++){
		c[++cl] = b[i]; pi[cl] = i;
		t[b[i]] = cl;
		j = i;
		while(b[i] == b[j]) j++;
		if(j-i > K){ printf("0\n"); return 0; }
		i = j-1;
	}
	LL ans = 1;
	pos[1] = 0;
	for(i = 2; i <= cl; i++){
		if(c[i-1] > c[i]){
			if(c[i%cl+1] > c[i]){
				if(pi[i] != (pi[i%cl+1]+n-K)%n){ printf("0\n"); return 0; }
			}
			pos[i] = pi[i];
		} else {
			if(c[i%cl+1] > c[i]){
				pos[i] = (pi[i%cl+1]+n-K)%n;
				if(pos[i] <= pos[i-1]){ printf("0\n"); return 0; }
			} else {
				pos[i] = -1;
				LL l = _max(pos[i-1]+1, (pi[i%cl+1]+n-K)%n), r = pi[i];
				ans = ans*(r-l+1)%Mod;
			}
		}
	}
	LL sy = 0;
	for(i = n; i >= 1; i--){
		if(t[i] == 0){ sy++; continue; }
		LL x = t[i];
		LL frt = x-1 <= 0 ? x+cl-1 : x-1;
		LL p = 0;
		if(pos[x] == -1) p = (pos[x%cl+1]+n-pos[frt]-2)%n;
		else if(c[frt] < c[x]) p = (pos[x]+n-pos[frt]-1)%n;
		else if(c[x%cl+1] < c[x]) p = (pos[x%cl+1]+n-pos[x]-1)%n;
		if(p > sy){ printf("0\n"); return 0; }
		ans = ans*jc[sy]%Mod*inv[sy-p]%Mod;
		sy -= p;
	}
	printf("%lld\n", ans);
	return 0;
}