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>
using ll = long long;
constexpr int MOD = 998244353;
struct data { int l, r; } rg[300005];
int arr[300005];
int main()
try
{
	// freopen("TK1-F.in", "r", stdin);
	int n, lst = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		rg[i].l = rg[i].r = -1;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", arr + i);
		if (i && arr[i] != arr[i - 1])
		{
			auto &it = rg[arr[i - 1]];
			if (~it.r)
				throw false;
			it = {lst, i - 1};
			lst = i;
		}
	}
	if (!lst)
	{
		if (arr[0] != 1)
			throw false;
		ll ans = 1;
		for (int i = 1; i <= n; i++)
			ans = ans * i % MOD;
		printf("%lld\n", ans);
		return 0;
	}
	arr[n] = arr[0];
	if (arr[n - 1] == arr[n])
		rg[arr[n]].l = lst;
	else
	{
		auto &it = rg[arr[n - 1]];
		if (~it.r)
			throw false;
		it = {lst, n - 1};
	}
	if (-1 == rg[1].r)
		throw false;
	auto calc_len = [&] (data & a) { return a.r - a.l + 1 + (a.l <= a.r ? 0 : n); };
	int k = calc_len(rg[1]), rem = 0;
	ll ans = 1;
	for (int i = 1; i <= n; i++)
	{
		if (-1 == rg[i].r)
		{
			ans = ans * rem-- % MOD;
			continue;
		}
		int l = rg[i].l, r = rg[i].r, len = calc_len(rg[i]);
		bool x = (arr[r + 1 - (r + 1 == n ? n : 0)] < i);
		bool y = (arr[l - 1 + (!l ? n : 0)] < i);
		if (len > k || (!x && !y && len != k))
			throw false;
		if (x && y)
		{
			rem += k + len - 2;
			ans = ans * (k - len + 1) % MOD;
		}
		else if (x || y)
			rem += len - 1;
	}
	printf("%lld\n", ans);
	return 0;
}
catch (bool)
{
	puts("0");
	return 0;
}