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:
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int MAXN = 320000;
const ll MOD = 998244353;

int n;
int a[MAXN];
int was[MAXN];

void no() {
	cout << 0 << "\n";
	exit(0);
}

int lb[MAXN];
int rb[MAXN];
int pr[MAXN];
int nx[MAXN];
int mx[MAXN];
int cc[MAXN];

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i], --a[i];
	int cnt = 0;
	for (int i = 0; i < n; ++i)
		if (a[i] == 0)
			++cnt;
	if (cnt == n) {
		ll ans = 1;
		for (int i = 1; i <= n; ++i)
			ans = (ans * i) % MOD;
		cout << ans << "\n";
		return 0;
	}
	if (cnt == 0)
		no();
	for (int i = 0; i + 1 < n; ++i) {
		if (a[i] != 0 && a[i + 1] == 0) {
			rotate(a, a + i + 1, a + n);
			break;
		}
	}
	if (a[0] != 0)
		no();
	for (int i = 0; i < n; ++i) {
		if (i != 0 && a[i - 1] == a[i])
			continue;
		if (was[a[i]])
			no();
		was[a[i]] = 1;
	}
	fill(lb, lb + n, n);
	fill(rb, rb + n, -1);
	for (int i = 0; i < n; ++i)
		lb[a[i]] = min(lb[a[i]], i), rb[a[i]] = max(rb[a[i]], i);
	vector<int> st;
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && a[st.back()] <= a[i])
			st.pop_back();
		if (st.empty())
			pr[i] = -1;
		else
			pr[i] = st.back();
		st.push_back(i);
	}
	st.clear();
	for (int i = n - 1; i >= 0; --i) {
		while (!st.empty() && a[st.back()] <= a[i])
			st.pop_back();
		if (st.empty())
			nx[i] = n;
		else
			nx[i] = st.back();
		st.push_back(i);
	}
	deque<int> dq;
	for (int i = n - 1; i >= 0; --i) {
		if (i + cnt < n && dq.front() == a[i + cnt])
			dq.pop_front();
		while (!dq.empty() && dq.back() < a[i])
			dq.pop_back();
		dq.push_back(a[i]);
		mx[i] = dq.front();
		++cc[mx[i]];
	}
	ll ans = 1;
	for (int i = 0; i < n; ++i) {
		if (lb[i] == n)
			continue;
		int l = rb[i] - (cnt - 1);
		int r = lb[i];
		if (nx[rb[i]] != n)
			r = min(r, nx[rb[i]] - cnt);
		if (pr[lb[i]] != -1)
			l = max(l, pr[lb[i]] + 1);
		if (l > r)
			no();
		ans = ans * (r - l + 1) % MOD;
		--cc[mx[l]];
	}
	int now = 0;
	for (int i = 0; i < n; ++i) {
		now += cc[i];
		if (lb[i] != n)
			continue;
		if (now <= 0)
			no();
		ans = (ans * now) % MOD;
		--now;
	}
	cout << ans << "\n";
	return 0;
}