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>
const int N = 300032;
typedef long long ll;
const ll MOD = 998244353;

ll factor(int n) {
	ll s = 1;
	while (n > 1) s = s * n-- %MOD;
	return s;
}

struct range {
	int l, r;
	range() {}
	range(int l, int r): l(l), r(r) {}
	int len();
	void ins();
} rg[N];

int a[N], n, k, fre = 0;
ll ans = 1;

inline int nxt(int i) {if (++i >= n) i -= n; return i;}
inline int pre(int i) {if (--i <  0) i += n; return i;}
inline int range::len() {int d = r-l+1; if (d < 0) d += n; return d;}

inline void range::ins() {
	int flag = (a[pre(l)] < a[l]) + (a[nxt(r)] < a[r]), d = len();
	if (flag ? d > k : d != k) puts("0"), exit(0);
	if (flag == 1) fre += d - 1;
	else if (flag == 2) {
		fre += k + d - 2;
		ans = ans * (k + 1 - d) %MOD;
	}
}

int main() {
	memset(rg, -1, sizeof rg);
	scanf("%d",&n);
	int l = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d",a+i);
		if (i && a[i] != a[i-1]) {
			auto &t = rg[a[i-1]];
			if (~t.r) {puts("0"); return 0;}
			t = range(l, i-1), l = i;
		}
	}
	if (!l) {
		if (*a != 1) puts("0");
		else printf("%lld\n",factor(n));
		return 0;
	}
	a[n] = a[0];
	if (a[n-1] == a[0]) rg[a[0]].l = l;
	else {
		auto &t = rg[a[n-1]];
		if (~t.r) {puts("0"); return 0;}
		else t = range(l, n-1);
	}

	if (rg[1].r == -1) {puts("0"); return 0;}
	k = rg[1].len();

	for (int i = 1; i <= n; i++)
		if (~rg[i].r) rg[i].ins();
		else ans = ans * fre-- %MOD;
	printf("%lld\n",ans);
	return 0;
}