cho.sh

Perfect Permutation 2

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

Medium7CombinatoricsGreedyMathImplementationNo attempts yetTime limit2sMemory limit128 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.

  1. B[0] = 0
  2. 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.

AB
0, 1, 20, 0, 0
0, 2, 10, 0, 0
1, 0, 20, 1, 0
1, 2, 00, 1, 2
2, 0, 10, 2, 1
2, 1, 00, 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.