E - Permutation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 7

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

1, 2, \ldots, N の順列 A_1, A_2, \ldots, A_N が与えられます。

各整数 1 \leq i \leq N に対して、次の条件を満たす 1 以上の整数 j として考えられる最小の値を求めてください。

  • x = i とする。xA_x で置き換えるという操作をちょうど j 回行った後、x = i となる。

制約

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq N
  • A_i \neq A_j (i \neq j)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

1, 2, \ldots, N のそれぞれに対して、この順に、問題文中の条件を満たす 1 以上の整数 j として考えられる最小の値を出力せよ。


入力例 1

6
1 3 2 5 6 4

出力例 1

1 2 2 3 3 3
  • i = 1 のとき A_1 = 1 であるので、j = 1 が条件を満たす最小の値です。
  • i = 2 のとき A_2 = 3, A_3 = 2 であるので、j = 2 が条件を満たす最小の値です。
  • i = 3 のとき A_3 = 2, A_2 = 3 であるので、j = 2 が条件を満たす最小の値です。
  • i = 4 のとき A_4 = 5, A_5 = 6, A_6 = 4 であるので、j = 3 が条件を満たす最小の値です。
  • i = 5 のとき A_5 = 6, A_6 = 4, A_4 = 5 であるので、j = 3 が条件を満たす最小の値です。
  • i = 6 のとき A_6 = 4, A_4 = 5, A_5 = 6 であるので、j = 3 が条件を満たす最小の値です。

入力例 2

3
3 2 1

出力例 2

2 1 2

入力例 3

2
1 2

出力例 3

1 1

Score : 7 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a permutation A_1, A_2, \ldots, A_N of 1, 2, \ldots, N.

For each integer 1 \leq i \leq N, find the minimum integer j not less than 1 that satisfies the following condition:

  • If we let x = i and then replace x with A_x exactly j times, we have x = i.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq N
  • A_i \neq A_j (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

For each of the integers 1, 2, \ldots, N, in this order, print the minimum integer j not less than 1 that satisfies the condition in Problem Statement.


Sample Input 1

6
1 3 2 5 6 4

Sample Output 1

1 2 2 3 3 3
  • For i = 1: Since A_1 = 1, j = 1 is the minimum value of j satisfying the condition.
  • For i = 2: Since A_2 = 3, A_3 = 2, j = 2 is the minimum value of j satisfying the condition.
  • For i = 3: Since A_3 = 2, A_2 = 3, j = 2 is the minimum value of j satisfying the condition.
  • For i = 4: Since A_4 = 5, A_5 = 6, A_6 = 4, j = 3 is the minimum value of j satisfying the condition.
  • For i = 5: Since A_5 = 6, A_6 = 4, A_4 = 5, j = 3 is the minimum value of j satisfying the condition.
  • For i = 6: Since A_6 = 4, A_4 = 5, A_5 = 6, j = 3 is the minimum value of j satisfying the condition.

Sample Input 2

3
3 2 1

Sample Output 2

2 1 2

Sample Input 3

2
1 2

Sample Output 3

1 1