链接: https://cses.fi/problemset/task/3398

板块: Mathematics

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有一个已排序的数组 $[1,2,\dots,n]$ 和一个排列 $p_1,p_2,\dots,p_n$。每一轮，所有元素根据排列移动：位于位置 $i$ 的元素移动到位置 $p_i$。

经过多少轮后，数组会首次再次变为有序？

输入

第一行包含一个整数 $n$。

下一行包含 $n$ 个整数 $p_1,p_2,\dots,p_n$。

输出

输出轮次数量对 $10^9+7$ 取模的结果。

数据范围

$1 \le n \le 2 \cdot 10^5$

样例输入

8
5 3 2 6 4 1 8 7

样例输出

4