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 <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD 998244353
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, A[303030], len;
int cnt[303030];
vector<int> seq;

vector<int> locs[303030];

int jmps[303030];
int sums = 0;

int &get(int p)
{
	if (p < 0) return jmps[p + N];
	if (p >= N) return jmps[p - N];
	return jmps[p];
}
void updsums(int l, int md)
{
	sums += md * max(l - len + 1, 0);
}
void activate(int p)
{
	//printf("ac %d\n", p);
	if (get(p) == (N - 1)) {
		sums = N;
		return;
	}

	int llen = get(p), rlen = get(p + 1);
	updsums(llen, -1);
	updsums(rlen, -1);
	int totlen = 1 + llen + rlen;
	updsums(totlen, 1);
	get(p) = 0;
	get(p + 1) = 0;
	get(p - llen) = totlen;
	get(p + 1 + rlen) = totlen;
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", A + i);

	len = 0;
	for (int i = 0; i < N; ++i) cnt[A[i]]++;
	for (int i = 1; i <= N; ++i) len = max(len, cnt[i]);

	if (len == N) {
		if (cnt[1] != N) {
			puts("0"); return 0;
		}
		i64 ret = 1;
		for (int i = 1; i <= N; ++i) ret = ret * i % MOD;
		printf("%lld\n", ret);
		return 0;
	}
	if (cnt[1] != len) {
		puts("0"); return 0;
	}
	int sep = 0;
	for (int i = 0; i < N; ++i) {
		if (A[i] != A[(i + 1) % N]) sep = (i + 1) % N;
	}
	for (int i = 0; i < N; ++i) seq.push_back(A[(sep + i) % N]);
	for (int i = 0; i < N; ++i) A[i] = seq[i];

	vector<bool> app(N + 1, false);
	for (int i = 0; i < N; ++i) {
		if (i > 0 && A[i] != A[i - 1] && app[A[i]]) {
			puts("0"); return 0;
		}
		//printf("%d\n", A[i]);
		app[A[i]] = true;
	}

	for (int i = 0; i < N; ++i) locs[A[i]].push_back(i);

	for (int i = 0; i < N; ++i) jmps[i] = 0;

	i64 ret = 1;
	for (int i = 1; i <= N; ++i) {
		if (i == N) {
			// do nothing
			continue;
		}
		int cur = sums;
		int cur2 = sums;
		//printf("%d %d %d\n", sums, len, locs[i].size());

		//for (int i = 0; i < N; ++i) printf("%d ", jmps[i]); puts("");
		if (locs[i].size() != 0) {
			int lf = locs[i][0], rg = locs[i].back();
			//printf("a %d %d\n", lf, rg);
			if (get(lf) == 0 && get(rg + 1) == 0) {
				if (rg - lf != len - 1) {
					puts("0");
					return 0;
				}
			} else if (get(lf) == 0 || get(rg + 1) == 0) {
				ret = ret;
			} else {
				ret = ret * (len - (rg - lf)) % MOD;
			}
		} else {
			ret = ret * (sums - i + 1) % MOD;
		}
		for (int l : locs[i]) activate(l);
	}
	printf("%lld\n", ret);

	return 0;
}