Problem Background

Alice and Bob are playing a game.

Problem Description

Alice provides a permutation of numbers from $1$ to $n$ to represent a function $y = f(x)$, where the $i$-th number given is $f(i)$.

Now, Bob needs to provide a function $y = g(x)$ with the smallest possible lexicographical order 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)$ sequentially.

Output Format

A single line containing $n$ integers, representing $g(1), g(2), \cdots, g(n)$ sequentially.

Sample Input and Output

Sample Input #1

5
1 2 3 4 5

Sample Output #1

1 1 1 1 1

Sample Input #2

5
2 3 4 5 1

Sample Output #2

1 2 3 4 5

Notes

Sample 1 Explanation

• $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 Explanation

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

Data Size and Constraints

For $30\%$ of the data, $n \le 5$.
For $60\%$ of the data, $n \le 10^3$.
For $100\%$ of the data, $1 \le n \le 8 \times 10^5$.

见题面 Input 部分

见题面 Output 部分