Xét một bảng lưới $N \times N$ mà các ô chứa các giá trị đôi một khác nhau. Ta định nghĩa hai phép toán $\text{RowShift}(r)$ và $\text{ColShift}(c)$ như sau:

• $\text{RowShift}(r)$: Dịch chuyển mỗi phần tử ở hàng $r$ sang phải một ô, trong đó phần tử ngoài cùng bên phải chuyển về ô ngoài cùng bên trái.
• $\text{ColShift}(c)$: Dịch chuyển mỗi phần tử ở cột $c$ xuống dưới một ô, trong đó phần tử dưới cùng chuyển lên ô trên cùng.

Cho một hoán vị $(P_1, P_2, \dots, P_N)$ của $(1, 2, \dots, N)$, việc thực hiện lần lượt $2N$ phép toán sau đây theo thứ tự được gọi là một quy trình:

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

Sau khi lặp lại quy trình đủ nhiều lần, bảng lưới chắc chắn sẽ trở về trạng thái ban đầu. Hãy tìm số lần lặp lại tối thiểu cần thiết. Vì đáp án có thể rất lớn, hãy in ra phần dư khi chia cho $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$. ($1 \le N \le 200\,000$)

Dòng thứ hai chứa $N$ số nguyên $P_1, P_2, \dots, P_N$ cách nhau bởi dấu cách. $(P_1, P_2, \dots, P_N)$ là một hoán vị của $(1, 2, \dots, N)$.

Dữ liệu ra

In ra phần dư của số lần lặp lại quy trình tối thiểu khi chia cho $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

2
1 2

Dữ liệu ra 1

3

Dữ liệu vào 2

3
1 3 2

Dữ liệu ra 2

3