Perfect Permutation 2

Time limit2sMemory limit128 MB

Summary

Given a permutation P, find a permutation Q minimizing mismatches with P such that repeatedly applying Q from 0 visits every index exactly once.

Level: Medium7 of 10
Topics: Combinatorics, Greedy, Math, Implementation
Solved: No attempts yet

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.

Examples6

Example 1
Input
```
6
4 0 5 2 1 3
```
Expected output
```
2 0 5 4 1 3
```
Example 2
Input
```
3
2 0 1
```
Expected output
```
2 0 1
```
Example 3
Input
```
8
2 7 3 0 6 4 5 1
```
Expected output
```
1 7 3 0 6 2 5 4
```

Example 4

Input

13
11 8 10 1 5 4 0 7 3 9 12 6 2

Expected output

1 8 10 2 5 7 0 9 3 11 12 6 4

Example 5
Input
```
6
0 1 4 2 3 5
```
Expected output
```
1 2 4 5 3 0
```
Example 6
Input
```
8
0 2 6 5 7 3 1 4
```
Expected output
```
1 2 6 5 7 4 3 0
```