Lexicographically Smallest Commuting Permutation

Alice provides a permutation of \(1\) to \(n\), which defines a function \(y=f(x)\) in the following way: the \(i\)-th number in the permutation is \(f(i)\). Bob is given this function \(f\) and must find a permutation \(g\) such that for every \(1 \leq i \leq n\), the condition

\[ f(g(i)) = g(f(i)) \]

holds. Among all permutations \(g\) satisfying this property, Bob must output the lexicographically smallest one.

Note: The identity permutation \(g(i)=i\) always satisfies \(f(g(i)) = g(f(i))\) because \(f(i)=f(i)\). Since the identity permutation is also lexicographically smallest, it will be the required answer.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) \((1 \leq n \leq 10^5)\), representing the number of elements in the permutation.
2. The second line contains \(n\) space-separated integers representing the permutation \(f\), where the \(i\)-th number is \(f(i)\).

outputFormat

Output a single line containing \(n\) space-separated integers, representing the lexicographically smallest permutation \(g\) that satisfies \(f(g(i)) = g(f(i))\) for all \(1 \leq i \leq n\).

sample

1
1

1