Description

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))$.

Input Format

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

Output Format

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

5
1 2 3 4 5

1 1 1 1 1

5
2 3 4 5 1

1 2 3 4 5

Hint

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