Ұяшықтарында қос-қостан әртүрлі мәндер жазылған $N \times N$ торды қарастырайық. Екі амалды — $\text{RowShift}(r)$ және $\text{ColShift}(c)$ — келесідей анықтаймыз:

• $\text{RowShift}(r)$: $r$-жолдың әрбір элементін оңға қарай бір ұяшыққа ығыстыру, бұл ретте ең оң жақтағы элемент ең сол жақтағы ұяшыққа ауысады.
• $\text{ColShift}(c)$: $c$-бағанның әрбір элементін төмен қарай бір ұяшыққа ығыстыру, бұл ретте ең төменгі элемент ең жоғарғы ұяшыққа ауысады.

$(1, 2, \dots, N)$ жиынының $(P_1, P_2, \dots, P_N)$ алмастыруы берілгенде, келесі $2N$ амалды ретімен орындау бір процедура деп аталады:

• $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)$

Процедураны жеткілікті рет қайталағаннан кейін, тор міндетті түрде бастапқы күйіне қайта оралады. Қажетті ең аз қайталау санын табыңыз. Жауап өте үлкен болуы мүмкін болғандықтан, оны $998\,244\,353$ санына бөлгендегі қалдықты шығарыңыз.

Кіріс деректер

Бірінші жолда бүтін $N$ саны беріледі. ($1 \le N \le 200\,000$)

Екінші жолда бос орын арқылы бөлінген $N$ бүтін сан $P_1, P_2, \dots, P_N$ беріледі. $(P_1, P_2, \dots, P_N)$ — $(1, 2, \dots, N)$ жиынының алмастыруы.

Шығыс деректер

Процедураны қайталаудың ең аз санын $998\,244\,353$ санына бөлгендегі қалдықты шығарыңыз.

Мысалдар

Кіріс деректер 1

2
1 2

Шығыс деректер 1

3

Кіріс деректер 2

3
1 3 2

Шығыс деректер 2

3