Lítum á $N \times N$ grind þar sem reitirnir innihalda tvenndarlega ólík gildi. Við skilgreinum tvær aðgerðir, $\text{RowShift}(r)$ og $\text{ColShift}(c)$, sem hér segir:

• $\text{RowShift}(r)$: Hliðra hverju staki í röð $r$ um einn reit til hægri, þannig að stakið lengst til hægri færist í reitinn lengst til vinstri.
• $\text{ColShift}(c)$: Hliðra hverju staki í dálki $c$ um einn reit niður á við, þannig að neðsta stakið færist í efsta reitinn.

Gefin er umröðun $(P_1, P_2, \dots, P_N)$ á $(1, 2, \dots, N)$, og að framkvæma eftirfarandi $2N$ aðgerðir í röð kallast ein lotuaðgerð:

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

Eftir að lotuaðgerðin hefur verið endurtekin nægilega oft er tryggt að grindin komist aftur í upphaflegt ástand. Finndu lágmarksfjölda endurtekninga sem þarf. Þar sem svarið getur verið mjög stórt skaltu prenta það módúló $998\,244\,353$.

Inntak

Fyrsta línan inniheldur heiltölu $N$. ($1 \le N \le 200\,000$)

Önnur línan inniheldur $N$ heiltölur $P_1, P_2, \dots, P_N$, aðskildar með bilum. $(P_1, P_2, \dots, P_N)$ er umröðun á $(1, 2, \dots, N)$.

Úttak

Prentaðu lágmarksfjölda skipta sem endurtaka þarf lotuaðgerðina, módúló $998\,244\,353$.

Dæmi

Inntak 1

2
1 2

Úttak 1

3

Inntak 2

3
1 3 2

Úttak 2

3