Рассмотрим таблицу размера $N \times N$, в клетках которой записаны попарно различные значения. Определим две операции, $\text{RowShift}(r)$ и $\text{ColShift}(c)$, следующим образом:

• $\text{RowShift}(r)$: сдвинуть каждый элемент строки $r$ на одну клетку вправо, при этом самый правый элемент перемещается в самую левую клетку.
• $\text{ColShift}(c)$: сдвинуть каждый элемент столбца $c$ на одну клетку вниз, при этом самый нижний элемент перемещается в самую верхнюю клетку.

Дана перестановка $(P_1, P_2, \dots, P_N)$ чисел $(1, 2, \dots, 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