问题 B: 换位置游戏

时间限制: 1 Sec 内存限制: 128 MB

提交: 64 解决: 11

[提交][状态][讨论版]

题目描述

N个小朋友（编号为1到N）正在玩一个换位置游戏。从左到右依次排列着N个凳子（编号为1到N，最左边的为1号凳子，最右边的为N号凳子），每个凳子上都有一个数字（凳脚处红色数字），每个数字互不相同，且都是不超过N的正整数。 游戏开始前，1号小朋友坐在1号凳子上，2号小朋友坐在2号凳子上，然后依次下去，N号小朋友坐在N号凳子上。比如当N=4时，游戏开始前小朋友们坐凳子的状态如下图1所示：

坐定后，游戏开始。每位小朋友看一下自己坐的凳子凳脚处的数字，然后根据这个数字找到相应号码的凳子。比如上面的例子，1号小朋友凳脚处数字是3，所以他到3号凳子上坐下，2号小朋友凳脚处数字是1，所以他到1号凳子坐下，3号小朋友凳脚处数字是2，所以他到2号凳子坐下，4号小朋友凳脚处数字是4，所以他到4号凳子坐下。经过一轮换位置以后，4个小朋友坐凳子的状态如下图2所示：

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

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

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

输入

输入共2行。 第1行是一个整数N（1≤N≤1000），表示参加游戏的小朋友人数，当然也表示凳子的数目。 第2行N个互不相同的正整数Ki（1≤Ki≤N，且1≤i≤N），Ki表示第i把凳子凳脚处的数字。

输出

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

样例输入

3

1 2 3

5

2 3 4 5 1

样例输出

1

5

提示

【样例1解释】 输入有3把凳子。1号凳子凳脚处的数字为1，2号凳子凳脚处的数字为2，3号凳子凳脚处的数字为3。第1轮换位置后，1号小朋友仍然坐在1号凳子上，2号小朋友仍然坐在2号凳子上，3号小朋友仍然坐在3号凳子上。所以经过1轮就回到了游戏开始前状态。

【样例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

【数据范围约定】

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