Tenka1 Programmer Contest - Circular

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

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
from operator import itemgetter
MOD = 998244353
(N, *A) = map(int, read().split())
T = A.count(1)
if T == 0:
	print(0)
	exit()
if T == 1:
	answer = 1 if len(set(A)) == N else 0
	print(answer)
	exit()
if T == N:
	answer = 1
	for n in range(1, N + 1):
		answer *= n
		answer %= MOD
	print(answer)
	exit()
n = A.index(1)
while A[n - 1] == 1:
	n -= 1
A = A[n:] + A[:n]
L = [0] * (N + 1)
R = [-1] * (N + 1)
ctr = [0] * (N + 1)
nums = []
prev = 0
for (i, x) in enumerate(A):
	ctr[x] += 1
	R[x] = i
	if prev != x:
		nums.append(x)
		L[x] = i
		prev = x
if any((y - x + 1 != z for (x, y, z) in zip(L, R, ctr))):
	print(0)
	exit()
if any((x > T for x in ctr[2:])):
	print(0)
	exit()
free = [0] * (N + 1)
answer = 1
for (x, y, z) in zip(nums, nums[1:], nums[2:] + [1]):
	if x > y < z:
		if ctr[y] != T:
			answer = 0
			break
	elif x < y < z:
		free[y] += ctr[y] - 1
	elif x > y > z:
		free[y] += ctr[y] - 1
	else:
		answer *= T + 1 - ctr[y]
		answer %= MOD
		free[y] += ctr[y] + T - 2
f = 0
for n in range(1, N + 1):
	if ctr[n] >= 1:
		f += free[n]
		continue
	answer *= f
	answer %= MOD
	f -= 1
print(answer)