题目描述

N 个小朋友（编号为 1 到 N ）正在玩一个换位置游戏。从左到右依次排列着 N 个凳子 （编号为 1 到 N ，最左边的为 1 号凳子，最右边的为 N 号凳子），每个凳子上都有一个数字 （凳脚处红色数字），每个数字互不相同，且都是不超过 N 的正整数。

游戏开始前， 1 号小朋友坐在 1 号凳子上， 2 号小朋友坐在 2 号凳子上， 然后依次下去， N 号小朋友坐在 N 号凳子上。

游戏开始后，小朋友看看自己凳子凳脚处的数字，坐到相应的位置上，这是第一轮。

坐定后，每位小朋友再看一下自己凳脚的数字，按照凳脚的数字再继续换位置，第二轮 换位置的结果如下图：

然后又如此操作，直到每小朋友坐到了他原来的位置，游戏结束。

从上面的过程我们可以发现，从游戏开始经过 3 轮换位置后又回到了游戏开始前坐凳子的状态，但当 N 很大的时候，这个换位置过程非常复杂，请编程帮忙计算一下最少需要经过多少轮换位置才能回到游戏开始前坐凳子的状态。

输入格式

第 1 行是一个整数 N ( 1 ≤ N ≤ 1000 )，表示参加游戏的小朋友人数，当然也表示凳子的数目。

第 2 行 N 个互不相同的正整数 $K_i$ ( 1 ≤ $K_i$ ≤ N ，且 1 ≤ i ≤ N ) , $K_i$ 表示第 i 把凳子凳脚处的数字。

数据范围

对于 60% 的数据， 1 ≤ N ≤ 500 ，且最少需要交换的轮数不超过 10000 。

对于 100% 的数据， 1 ≤ N ≤ 1000 ，且最少需要交换的轮数不超过 20000000 。

输出格式

表示小朋友们通过换位置后回到游戏开始前坐凳子的状态最少需要经过多少轮。测试数据保证输出的结果不超出 20000000 。

样例

3
1 2 3

1

5
2 3 4 5 1

5

样例解释

1. 样例 1 :

输入有 3 把凳子。 1 号凳子凳脚处的数字为 1 , 2 号凳子凳脚处的数字为 2 , 3 号凳子凳脚处的数字为 3 。

第 1 轮换位置后， 1 号小朋友仍然坐在 1 号凳子上， 2 号小朋友仍然坐在 2 号凳子上， 3 号小朋友仍然坐在3号凳子上。

所以经过 1 轮就回到了游戏开始前状态。

2. 样例 2 :

游戏中有 5 个小朋友 5 把凳子， 1 到 5 号凳子凳脚处的数字依次为： 2 3 4 5 1 。

第 1 轮换位置后， 1 到 5 号凳子上小朋友的编号为： 5 1 2 3 4

第 2 轮换位置后， 1 到 5 号凳子上小朋友的编号为： 4 5 1 2 3

第 3 轮换位置后， 1 到 5 号凳子上小朋友的编号为： 3 4 5 1 2

第 4 轮换位置后， 1 到 5 号凳子上小朋友的编号为： 2 3 4 5 1

第 5 轮换位置后， 1 到 5 号凳子上小朋友的编号为： 1 2 3 4 5