不久前,Leonid 已经知道幂等函数了。在集合 {1, 2, ..., n} 上定义的幂等函数是这样的函数 $$g:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$$,对于任何 $$x \in \{1, 2, \ldots, n\}$$,公式 g(g(x)) = g(x) 成立。
我们将函数 f 对值 x 应用 k 次表示为 f(k)(x)。更正式地说,对于每个 k > 1,f(1)(x) = f(x)、f(k)(x) = f(f(k - 1)(x))。
给你一些函数 $$f: \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$$。您的任务是找到最小正整数 k,使得函数 f(k)(x) 具有幂等性。
输入
在输入的第一行中有一个整数 n (1 ≤ n ≤ 200) — 函数 f 域的大小。
在第二行中,f(1), f(2), ..., f(n) (对于每个 1 ≤ i ≤ n,1 ≤ f(i) ≤ n),函数的值。
输出
输出最小 k 使得函数 f(k)(x) 是幂等的。
示例
输入 #1
4 1 2 2 4
输出 #1
1
输入 #2
3 2 3 3
输出 #2
2
输入 #3
3 2 3 1
输出 #3
3
注意
在第一个示例测试函数中,f(x) = f(1)(x) 已经是幂等的,因为 f(f(1)) = f(1) = 1、f(f(2)) = f(2) = 2、f(f(3)) = f(3) = 2、f(f(4)) = f(4) = 4。
在第二个样本测试中:
- 函数 f(x) = f(1)(x) 不是幂等的,因为 f(f(1)) = 3 但 f(1) = 2;
- 函数 f(x) = f(2)(x) 是幂等的,因为对于任何 x,f(2)(x) = 3 成立,因此 f(2)(f(2)(x)) = 3 也成立。
在第三个样本测试中:
- 函数 f(x) = f(1)(x) 不是幂等的,因为 f(f(1)) = 3 但 f(1) = 2;
- 函数 f(f(x)) = f(2)(x) 不是幂等的,因为 f(2)(f(2)(1)) = 2 但 f(2)(1) = 3;
- 函数 f(f(f(x))) = f(3)(x) 是幂等的,因为它是恒等函数: f(3)(x) = x 对于任何 $$x \in \{1, 2, 3\}$$ 意味着公式 f(3)(f(3)(x)) = f(3)(x) 也成立。