Considérons une grille $N \times N$ dont les cases contiennent des valeurs deux à deux distinctes. On définit deux opérations, $\text{RowShift}(r)$ et $\text{ColShift}(c)$, comme suit :

• $\text{RowShift}(r)$ : décaler chaque élément de la ligne $r$ d'une case vers la droite, l'élément le plus à droite passant à la case la plus à gauche.
• $\text{ColShift}(c)$ : décaler chaque élément de la colonne $c$ d'une case vers le bas, l'élément le plus en bas passant à la case la plus en haut.

Étant donné une permutation $(P_1, P_2, \dots, P_N)$ de $(1, 2, \dots, N)$, effectuer les $2N$ opérations suivantes dans l'ordre est appelé une procédure :

• $1$-re : $\text{RowShift}(1)$
• $2$-e : $\text{ColShift}(P_1)$
• $3$-e : $\text{RowShift}(2)$
• $4$-e : $\text{ColShift}(P_2)$
• $\vdots$
• $2N - 1$-e : $\text{RowShift}(N)$
• $2N$-e : $\text{ColShift}(P_N)$

Après avoir répété la procédure suffisamment de fois, la grille revient nécessairement à son état initial. Trouvez le nombre minimum de répétitions nécessaires. Comme la réponse peut être très grande, affichez-la modulo $998\,244\,353$.

Entrée

La première ligne contient un entier $N$. ($1 \le N \le 200\,000$)

La deuxième ligne contient $N$ entiers $P_1, P_2, \dots, P_N$, séparés par des espaces. $(P_1, P_2, \dots, P_N)$ est une permutation de $(1, 2, \dots, N)$.

Sortie

Affichez le nombre minimum de fois que la procédure doit être répétée, modulo $998\,244\,353$.

Exemples

Entrée 1

2
1 2

Sortie 1

3

Entrée 2

3
1 3 2

Sortie 2

3