题目描述

有 $n$ 为同学和 $n$ 个篮球，人和球编号都为 $1...n$。开始时每个同学都手持与自己编号相同的球。现在要反复执行如下操作若干轮传球训练：每轮中， $i$ 号同学把当前手中的球（无论是几号球）传给 $a_i$ 号同学。保证 $1 \le a_i \le n$ 且互不相等，也就是每个同学每轮都会传出 $1$ 个球，并且也接到 $1$ 个球。

求至少连续进行几轮如上操作后，再次出现所有同学都持有与自己编号相同的球的情况。

输入格式

第一行一个正整数 $n$；

第二行 $n$ 个正整数 $a_1, a_2 \dots a_n$。

输出格式

一个正整数表示答案。

输入输出样例

输入样例1

6
3 6 4 1 2 5

输出样例1

3

提示：我们考虑第 $i$ 号球每轮在几号同学手里，这样会容易思考一些。如上述样例中

一轮后 $1 \dots 6$ 号球分别在 $3,6,4,1,2,5$ 号同学手里；

二轮后 $1 \dots 6$ 号球分别在 $4,5,1,3,6,1$ 号同学手里；

三轮后 $1 \dots 6$ 号球分别在 $1,2,3,4,5,6$ 号同学手里；

输入样例2

9
8 9 5 1 6 2 4 7 3

20

数据范围与提示

对于 $30\%$ 的数据， $n \le 3$;

对于 $60\%$ 的数据， $n \le 10$;

对于 $30\%$ 的数据， $a_i = i$;

对于 $30\%$ 的数据， $a_i = i\%n + 1$;

对于 $30\%$ 的数据， $a_i = (i + 1) \% n + 1$;

对于 $100\%$ 的数据， $1 \le n \le 20$，$1 \le a_i \le n$ 且互不相等;