Perfect Permutation 2

Time limit

Memory limit

128 MB

Problem

Let A be a permutation that contains every integer from 0 to N-1 exactly once. From A, define an array B of the same length as follows.

B[0] = 0
B[i] = A[B[i-1]] (1 ≤ i ≤ N-1)

If the resulting B is also a permutation, then A is called a perfect permutation.

The table below shows every permutation A of length 3 and its child array B. The permutations {1, 2, 0} and {2, 0, 1} are perfect because their child arrays are also permutations.

A	B
0, 1, 2	0, 0, 0
0, 2, 1	0, 0, 0
1, 0, 2	0, 1, 0
1, 2, 0	0, 1, 2
2, 0, 1	0, 2, 1
2, 1, 0	0, 2, 0

Given a permutation P of length N, output a perfect permutation Q whose difference from P is as small as possible. The difference between P and Q is the number of indices i for which P[i] and Q[i] are different.

Input

The first line contains the size N of the permutation (1 ≤ N ≤ 50). The second line contains N integers, the permutation P[0], P[1], ..., P[N-1], separated by spaces.

Output

Print a perfect permutation Q whose difference from P is minimum. If there are multiple possible Q, print the one whose child array B is lexicographically smallest.