Return to Original Position — Drum Beats Problem

Jack, a sports teacher at St. Patrick’s School, created a game for his students.

He lined up N students, each wearing a jersey numbered 1 to N, in increasing order.

In front of each student, there is a board showing a unique integer from 1 to N. These numbers form a permutation array B[].

After every drum beat, each student moves to the position indicated by the number on their current board.

This process keeps repeating until all students return to their original order (1 to N).

Your task is to find how many drum beats are required for the students to return to the original arrangement.

Example

Input

5
2 3 1 5 4

Output

6

Explanation

• Students move according to the board numbers after each drum beat.

• The positions keep changing following the permutation.

• After 6 beats, the arrangement becomes [1, 2, 3, 4, 5] again.

Therefore, the answer is 6.