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 <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 998244353;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i]; --A[i];
	}
	int ptr = -1;
	for (int i = 0; i < N; ++i) {
		if (A[(i + N - 1) % N] != 0 && A[i] == 0) {
			ptr = i;
		}
	}
	if (ptr == -1) {
		if (find(A.begin(), A.end(), 0) == A.end()) {
			cout << 0 << endl;
		}
		else {
			int fact = 1;
			for (int i = 1; i <= N; ++i) fact = (long long)(fact) * i % mod;
			cout << fact << endl;
		}
		return 0;
	}
	vector<int> shiftA(N);
	for (int i = 0; i < N; ++i) {
		shiftA[i] = A[(i + ptr) % N];
	}
	A = shiftA;
	vector<int> L(N, -1), R(N, -1);
	for (int i = 0; i < N; ++i) {
		if (L[A[i]] == -1) L[A[i]] = i;
		R[A[i]] = i;
	}
	int sum = 0;
	for (int i = 0; i < N; ++i) {
		if (R[i] != -1) ++R[i];
		sum += R[i] - L[i];
	}
	if (sum != N || L[0] == -1) {
		cout << 0 << endl;
	}
	else {
		int len = R[0] - L[0];
		bool ok = true;
		vector<int> cand(N, -1); cand[0] = 0;
		int ans = 1;
		for (int i = N - 1; i >= 1 && ok; --i) {
			if (L[i] == -1) {
				continue;
			}
			if (R[i] - L[i] > len) {
				ok = false;
				break;
			}
			int ln = A[L[i] - 1], rn = A[R[i] % N];
			cand[(ln > i ? L[i] : R[i] - len)] = i;
			if (ln > i && rn > i) {
				if (R[i] - L[i] != len) ok = false;
			}
			if (ln < i && rn < i) {
				ans = (long long)(ans) * (len - (R[i] - L[i]) + 1) % mod;
			}
		}
		vector<int> lmax(N), rmax(N);
		for (int i = 1; i < N; ++i) lmax[i] = (cand[i] == -1 ? lmax[i - 1] : cand[i]);
		if (cand[N - 1] != -1) rmax[N - 1] = cand[N - 1];
		for (int i = N - 2; i >= 0; --i) rmax[i] = (cand[i] == -1 ? rmax[i + 1] : cand[i]);
		vector<int> hist(N);
		for (int i = 0; i < N; ++i) {
			if (cand[i] == -1) {
				++hist[max(lmax[i], rmax[i])];
			}
		}
		int unused = 0;
		for (int i = 0; i < N; ++i) {
			unused += hist[i];
			if (L[i] == -1) {
				if (unused == 0) {
					ok = false;
					break;
				}
				ans = (long long)(ans) * unused % mod;
				--unused;
			}
		}
		cout << (ok ? ans : 0) << endl;
	}
	return 0;
}