E. Registros da roda

Time limit: 3000 msMemory limit: 256 MB

Uma roda tem $n$ posições numeradas de $1$ a $n$ . Colocam-se os números de $1$ a $n$ nas posições, cada número exatamente uma vez. Para cada par de posições vizinhas, incluindo a última e a primeira, registra-se o maior dos dois números. Os $n$ registros foram embaralhados.

Dados os registros $b_1,\ldots,b_n$ , conte quantas permutações $p_1,\ldots,p_n$ produzem exatamente esse multiconjunto, isto é, têm como registros os valores

$\max(p_1,p_2),\max(p_2,p_3),\ldots,\max(p_n,p_1).$

As posições são numeradas: permutações que diferem por rotação ou reflexão contam separadamente. Imprima a resposta módulo $998\,244\,353$ .

Input

A primeira linha contém $n$ ( $3\le n\le200\,000$ ).

A segunda linha contém $n$ inteiros $b_1,\ldots,b_n$ (). Os registros podem se repetir e não necessariamente estão ordenados.

Output

Imprima a quantidade de permutações possíveis, módulo $998\,244\,353$ . Se não houver nenhuma, imprima 0.

Samples

Sample 1

Input

3
2 3 3

Output

Todas as $3!=6$ permutações produzem esses registros.

Sample 2

Input

3
1 3 3

Output

O número $1$ nunca pode ser o maior entre dois números distintos de $1$ a $3$ .

Sample 3

Input

4
3 3 4 4

Output

Uma disposição é . Suas quatro rotações e as quatro rotações da disposição refletida são as oito possibilidades.