Problem:
 Score : 900 points    Problem Statement 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 .        Sample Input 1 3
1
2
1      Sample Output 1 2  (2,3,1) and (3,2,1) satisfy the condition.       Sample Input 2 5
3
1
4
1
5      Sample Output 2 0       Sample Input 3 8
4
4
4
1
1
1
2
2      Sample Output 3 24       Sample Input 4 6
1
1
6
2
2
2      Sample Output 4 0

Solution (Python):
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)