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 "bits//stdc++.h"
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 998244353;

#define rep(i,n) for (int i = 0; i < (n); i++)
#define ALL(v) v.begin(), v.end()
typedef pair<int, int> P;
ll mod_pow(ll a, ll n) {
	if (n == 0) return 1;
	if (n % 2 == 0) {
		ll tmp = mod_pow(a, n / 2);
		return (tmp * tmp) % MOD;
	}
	return (a * mod_pow(a, n - 1)) % MOD;
}

vector<ll> fact;
vector<ll> inv_fact;

void comb_init(int n) {
	fact.resize(n + 1);
	inv_fact.resize(n + 1);
	fact[0] = inv_fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv_fact[i] = (inv_fact[i - 1] * mod_pow(i, MOD - 2)) % MOD;
	}
}

struct UnionFind {
	vector<int> par;
	vector<int> size;
	vector<int> len;
	UnionFind(int n, deque<P> &dq) {
		par = vector<int>(n);
		for (int i = 0; i < n; i++) par[i] = i;
		size = vector<int>(n, 1);
		len = vector<int>(n);
		rep(i, n) len[i] = dq[i].second;
	}

	int find(int x) {
		if (x == par[x]) return x;
		return par[x] = find(par[x]);
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (size[x] < size[y]) {
			par[x] = y;
			size[y] += size[x];
			len[y] += len[x];
		}
		else {
			par[y] = x;
			size[x] += size[y];
			len[x] += len[y];
		}
	}
};
int A[300000];
int B[300000];
int appear[300001];
int count_pos(int i, int N, int X, UnionFind &U) {
	int len = U.len[U.find(i)];
	if (len == N) return N;
	return max(len - X + 1, 0);
}
int main() {
	int N;
	cin >> N;
	rep(i, N) cin >> A[i];
	int one = -1;
	rep(i, N) {
		if (A[i] == 1) {
			one = i;
			break;
		}
	}
	if (one == -1) {
		cout << 0 << endl;
		return 0;
	}
	rep(i, N) {
		B[i] = A[(i + one) % N];
	}
	deque<P> dq;
	int val = B[0], len = 1;
	for (int i = 1; i < N; i++) {
		if (B[i] != val) {
			dq.emplace_back(val, len);
			val = B[i];
			len = 1;
		}
		else {
			len++;
		}
	}
	dq.emplace_back(val, len);
	if (dq.size() > 1 && dq.back().first == 1) {
		dq[0].second += dq.back().second;
		dq.pop_back();
	}
	int X = dq[0].second;
	memset(appear, -1, sizeof(appear));
	rep(i, dq.size()) {
		if (appear[dq[i].first] != -1) {
			cout << 0 << endl;
			return 0;
		}
		else {
			appear[dq[i].first] = i;
		}
		if (dq[i].second > X) {
			cout << 0 << endl;
			return 0;
		}
	}
	comb_init(N);
	if (dq.size() == 1) {
		cout << fact[N] << endl;
		return 0;
	}
	UnionFind U(dq.size(), dq);
	ll ans = 1;
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		if (appear[i] == -1) {
			(ans *= sum - (i - 1)) %= MOD;
		}
		else {
			int prv = (appear[i] + dq.size() - 1) % dq.size();
			int nxt = (appear[i] + 1) % dq.size();
			if (dq[prv].first < i && dq[nxt].first < i) {
				(ans *= (X - dq[appear[i]].second + 1)) %= MOD;
			}
			else if (dq[prv].first > i && dq[nxt].first > i && dq[appear[i]].second != X) {
				cout << 0 << endl;
				return 0;
			}
			sum += count_pos(appear[i], N, X, U);
			if (dq[prv].first < i) {
				sum -= count_pos(prv, N, X, U);
				sum -= count_pos(appear[i], N, X, U);
				U.unite(prv, appear[i]);
				sum += count_pos(appear[i], N, X, U);
			}
			if (dq[nxt].first < i && !U.same(nxt, appear[i])) {
				sum -= count_pos(nxt, N, X, U);
				sum -= count_pos(appear[i], N, X, U);
				U.unite(nxt, appear[i]);
				sum += count_pos(appear[i], N, X, U);
			}
		}
	}
	cout << ans << endl;
}