P2582 Function

Alice and Bob play a game.

Alice gives a permutation of $1$ to $n$ representing a function $y=f(x)$, i.e., the $i$-th number given is $f(i)$. Now Bob needs to give a function $y=g(x)$ that is lexicographically as small as possible, such that for any $i$, $f(g(i))=g(f(i))$.

The first line contains an integer $n$. The second line contains $n$ integers, representing $f(1), f(2) \cdots f(n)$ in order.

Output one line containing $n$ integers, representing $g(1), g(2) \cdots g(n)$ in order.

Sample Explanation Sample 1 - $g(f(1))=f(g(1))=1$. - $g(f(2))=f(g(2))=1$. - $g(f(3))=f(g(3))=1$. - $g(f(4))=f(g(4))=1$. - $g(f(5))=f(g(5))=1$. Sample 2 - $g(f(1))=f(g(1))=2$. - $g(f(2))=f(g(2))=3$. - $g(f(3))=f(g(3))=4$. - $g(f(4))=f(g(4))=5$. - $g(f(5))=f(g(5))=1$. Constraints - For $30\%$ of the testdata, $n \le 5$. - For $60\%$ of the testdata, $n \le 10^3$. - For $100\%$ of the testdata, $1 \le n \le 8 \times 10^5$. Translated by ChatGPT 5