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 <algorithm>
using namespace std;
#pragma warning (disable: 4996)

vector<pair<int, int>> vec; vector<int> L;
long long N, A[300009], C[300009], s, mod = 998244353, V[300009]; bool used[300009];

void init() {
	vec.clear(); L.clear(); s = 0;
	for (int i = 0; i < 309; i++) { A[i] = 0; C[i] = 0; V[i] = 0; used[i] = false; }
}

long long solve_ans() {
	for (int i = 0; i < N; i++) { if (A[i] == 1) L.push_back(i); }
	if (L.size() == 0) {
		return 0;
	}
	else if (L.size() == N) {
		long long ans = 1;
		for (int i = 1; i <= N; i++) { ans *= i; ans %= mod; }
		return ans;
	}
	sort(L.begin(), L.end()); int I = -1;
	for (int i = 0; i < L.size(); i++) {
		int t1 = L[i], t2 = L[(i + 1) % L.size()]; if (i == L.size() - 1) t2 += N;
		if (t2 - t1 != 1) {
			if (I != -1) { return 0; }
			I = t2;
		}
	}
	for (int i = 0; i < N; i++) C[i] = A[(i + I) % N];

	vector<pair<int, int>>vec; int s = 0;
	for (int i = 0; i < N; i++) {
		if (C[i] != C[i + 1]) {
			if (used[C[s]] == true) {  return 0; }
			vec.push_back(make_pair(C[s], s)); used[C[s]] = true; s = i + 1;
		}
	}
	int Z = N; if (vec.size() >= 2) Z = vec[1].second;
	for (int i = 0; i < vec.size(); i++) {
		int p1 = vec[i].second, p2 = vec[(i + 1) % vec.size()].second; if (i == vec.size() - 1) p2 += N;
		if (p2 - p1 > Z) { return 0; }
	}

	long long FinalAns = 1;

	vector<pair<int, int>>vec2; vec2.push_back(make_pair(1, 0)); // (数, pos)
	for (int i = 1; i < vec.size(); i++) {
		int t1 = vec[i - 1].first, t2 = vec[i].first, t3 = vec[(i + 1) % vec.size()].first;

		if (t1 < t2 && t2 < t3) {
			int u = vec[i + 1].second; u -= Z;
			vec2.push_back(make_pair(t2, u));
		}
		if (t1 < t2 && t2 > t3) {
			int u = vec[i].second;
			int lens = vec[(i + 1) % vec.size()].second - vec[i].second; if (i == vec.size() - 1) lens += N;
			vec2.push_back(make_pair(t2, u));
			FinalAns *= (Z + 1LL - lens);
			FinalAns %= mod;
		}
		if (t1 > t2 && t2 < t3) {
			int lens = vec[i + 1].second - vec[i].second;
			if (lens != Z) {
				return 0;
			}
			vec2.push_back(make_pair(t2, vec[i].second));
		}
		if (t1 > t2 && t2 > t3) {
			int u = vec[i].second;
			vec2.push_back(make_pair(t2, u));
		}
	}
	vector<int>J;
	for (int i = 0; i < vec2.size(); i++) {
		int v1 = vec2[i].second + 1, v2 = vec2[(i + 1) % vec2.size()].second - 1; if (i == vec2.size() - 1) v2 += N;
		for (int j = v1; j <= v2; j++) J.push_back(max(vec2[i].first, vec2[(i + 1) % vec2.size()].first));
	}
	sort(J.begin(), J.end()); reverse(J.begin(), J.end());

	// 最後の数え上げ
	for (int i = 1; i <= N; i++) V[i] = 1;
	for (int i = 0; i < vec2.size(); i++) V[vec2[i].first] = 0;
	for (int i = N - 1; i >= 1; i--) V[i] += V[i + 1];

	for (int i = 0; i < J.size(); i++) {
		FinalAns *= (V[J[i]] - i);
		FinalAns %= mod;
	}
	return FinalAns;
}

int main() {
	//FILE *in = freopen("in1.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	cout << solve_ans() << endl;
	return 0;
}