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<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define vvvel vector<vvel>
void mmin(int &a, int b) { a = min(a, b); }
void mmax(int &a, int b) { a = max(a, b); }
void sor(vel &v) { sort(v.begin(), v.end()); }
signed main() {
	int p = 998244353;
	int n;
	cin >> n;
	vel a(n);
	int x = -1;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
	}
	vel qun(n);
	vel qko(n, 0);
	int si = 0;
	qun[0] = a[0];
	qko[0] = 1;
	for (int i = 1; i < n; i++) {
		if (a[i] != qun[si]) si++;
		qun[si] = a[i];
		qko[si]++;
	}
	if (qun[0] == qun[si] and si != 0) {
		qko[0] += qko[si]; si--;
	}
	vel un(si + 1);
	vel ko(si + 1);
	vel po(n, -1);
	for (int i = 0; i <= si; i++) {
		un[i] = qun[i];
		ko[i] = qko[i];
		po[un[i]] = i;
	}
	vel mu = un;
	sor(mu);
	int db = 0;
	for (int i = 0; i < si; i++) {
		if (mu[i] == mu[i + 1]) db = 1;
	}
	int mak1 = mu[si];
	if (db == 1) cout << 0 << endl;
	else {
		int ans = 1;
		vel ah(si + 1, 0);
		int ex = 0;
		if (po[0] == -1) {
			cout << 0 << endl;
			return 0;
		}
		int mes = ko[po[0]];
		for (int i = 0; i < n; i++) {
			int po1 = po[i];
			if (po1 == -1) {
				ans *= ex;
				ans = ans % p;
				ex--;
			}
			else {
				int ko1 = ko[po1];
				if (ko1 > mes) {
					ans = 0;
				}
				int xx = ah[(po1 + 1) % (si + 1)] + ah[(po1 + si) % (si + 1)];
				if (xx == 0) {
					if (ko1 == n) {
						ex = n - 1;
						ans *= n;
						ans = ans % p;
					}
					if (ko1 != mes) {
						ans = 0;
					}
				}
				if (xx == 1) {
					ex += ko1 - 1;
				}
				if (xx == 2) {
					if (i != mak1) {
						ex += ko1 + mes-2;
					}
					else {
						ex = n - i - 1;
					}
					ans *= (mes - ko1 + 1);
					ans = ans % p;
				}
				ah[po1] = 1;
			}
		}
		cout << ans << endl;
	}
	return 0;
}