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"
using namespace std;
int n;
int a[300010];
int l[300010], r[300010];
const int mod = 998244353;


int id(int x) {
	return ((x % n) + n) % n;
}
int size(int l, int r) {
	if(l == -1) return 0;
	int ans = 0;
	while(true) {
		int tmp = l;
		l = id(l + 1);
		++ans;
		if(tmp == r) break;
	}
	return ans;
}

int main(int argc, char const *argv[])
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	int shift = count(a, a + n, 1);
	if(shift == 0) {
		printf("0\n");
		exit(0);
	} else if (shift == n) {
		long long ans = 1;
		for(int i = 2; i <= n; i++) {
			ans *= i;
			ans %= mod;
		}
		printf("%lld\n", ans);
		exit(0);
	}
	int cur;	
	for(int i = 0; i < n; i++) {
		if(a[i] == 1) {
			cur = i;
			break;
		}
	}
	while(a[id(cur - 1)] == 1) {
		cur = id(cur - 1);
	} 
	memset(l, -1, sizeof l);
	memset(r, -1, sizeof r);

	while(true) {
		int val = a[cur];
		if(l[val] != -1) {
			printf("0\n");
			exit(0);
		}
		int tmp = cur;
		while(a[cur] == val) {
			cur = id(cur + 1);
		}
		l[val] = tmp;
		r[val] = id(cur - 1);
		if(a[cur] == 1) break; 
	}

	for(int i = 1; i <= n; i++) {
		// printf("%d %d %d\n", i, l[i], r[i]);
		if(size(l[i], r[i]) > shift) {
			printf("0\n");
			exit(0);
		} 
	}
	long long ans = 1;
	int cmp = 0;
	int tot = 0;
	for(int i = 1; i <= n; i++) {
		if(l[i] == -1) {
			ans *= (tot - (shift - 1) * cmp - (i - 1));
			ans %= mod;
			continue;
		}
		int sz = size(l[i], r[i]);
		if(a[id(l[i] - 1)] > i) {
			if(a[id(r[i] + 1)] > i) {
				++cmp;
				if(sz < shift) {
					printf("0\n");
					exit(0);
				}
			}
		} else if (a[id(r[i] + 1)] > i) {
		} else {
			--cmp;
			ans *= (shift - sz + 1);
			ans %= mod;
		}
		tot += sz;
	}
	printf("%lld\n", ans);
	return 0;
}