C - Inverse of Permutation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300300

問題文

1,2,,N1,2,\dots,N11 回ずつ現れる長さ NN の数列を「長さ NN の順列」と呼びます。
長さ NN の順列 P=(p1,p2,,pN)P = (p_1, p_2,\dots,p_N) が与えられるので、以下の条件を満たす長さ NN の順列 Q=(q1,,qN)Q = (q_1,\dots,q_N) を出力してください。

  • 全ての ii (1iN)(1 \leq i \leq N) に対して QQpip_i 番目の要素が ii である。

ただし、条件を満たす QQ は必ずただ 11 つ存在することが証明できます。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • (p1,p2,,pN)(p_1,p_2,\dots,p_N) は長さ NN の順列である。
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

NN
p1p_1 p2p_2 \dots pNp_N

出力

数列 QQ を空白区切りで 11 行で出力せよ。

q1q_1 q2q_2 \dots qNq_N

入力例 1Copy

Copy
3
2 3 1

出力例 1Copy

Copy
3 1 2

以下に説明する通り、 Q=(3,1,2)Q=(3,1,2) は条件を満たす順列です。

  • i=1i = 1 のとき pi=2,q2=1p_i = 2, q_2 = 1
  • i=2i = 2 のとき pi=3,q3=2p_i = 3, q_3 = 2
  • i=3i = 3 のとき pi=1,q1=3p_i = 1, q_1 = 3

入力例 2Copy

Copy
3
1 2 3

出力例 2Copy

Copy
1 2 3

全ての ii (1iN)(1 \leq i \leq N) に対して pi=ip_i = i が成り立つときは P=QP = Q になります。


入力例 3Copy

Copy
5
5 3 2 4 1

出力例 3Copy

Copy
5 3 2 4 1

Score : 300300 points

Problem Statement

We will call a sequence of length NN where each of 1,2,,N1,2,\dots,N occurs once as a permutation of length NN.
Given a permutation of length NN, P=(p1,p2,,pN)P = (p_1, p_2,\dots,p_N), print a permutation of length NN, Q=(q1,,qN)Q = (q_1,\dots,q_N), that satisfies the following condition.

  • For every ii (1iN)(1 \leq i \leq N), the pip_i-th element of QQ is ii.

It can be proved that there exists a unique QQ that satisfies the condition.

Constraints

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • (p1,p2,,pN)(p_1,p_2,\dots,p_N) is a permutation of length NN (defined in Problem Statement).
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN
p1p_1 p2p_2 \dots pNp_N

Output

Print the sequence QQ in one line, with spaces in between.

q1q_1 q2q_2 \dots qNq_N

Sample Input 1Copy

Copy
3
2 3 1

Sample Output 1Copy

Copy
3 1 2

The permutation Q=(3,1,2)Q=(3,1,2) satisfies the condition, as follows.

  • For i=1i = 1, we have pi=2,q2=1p_i = 2, q_2 = 1.
  • For i=2i = 2, we have pi=3,q3=2p_i = 3, q_3 = 2.
  • For i=3i = 3, we have pi=1,q1=3p_i = 1, q_1 = 3.

Sample Input 2Copy

Copy
3
1 2 3

Sample Output 2Copy

Copy
1 2 3

If pi=ip_i = i for every ii (1iN)(1 \leq i \leq N), we will have P=QP = Q.


Sample Input 3Copy

Copy
5
5 3 2 4 1

Sample Output 3Copy

Copy
5 3 2 4 1


2025-04-14 (Mon)
10:15:39 +00:00