F - Insert Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

空の配列 A があります。 i=1,2,\ldots,N の順に以下の操作を行います。

  • 数 i を、A の前から P_i 番目の位置になるように挿入する。
    • より正確には、「A の P_i-1 項目まで」「 i 」「A の P_i 項目以降」をこの順に連結したもので A を置き換える。

全ての操作を終えた後の A を出力してください。

制約

  • 1 \leq N \leq 5\times 10^5
  • 1 \leq P_i \leq i
  • 入力は全て整数である

入力

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

N
P_1 P_2 \ldots P_N

出力

全ての操作を終えた後の A を (A_1,\ldots,A_N) とするとき、A_1,\ldots,A_N をこの順に空白区切りで出力せよ。

入力例 1

4
1 1 2 1

出力例 1

4 2 3 1

操作は以下のように行われます。

  • 数 1 を、A の前から 1 番目の位置になるように挿入する。 A=(1) となる。
  • 数 2 を、A の前から 1 番目の位置になるように挿入する。 A=(2,1) となる。
  • 数 3 を、A の前から 2 番目の位置になるように挿入する。 A=(2,3,1) となる。
  • 数 4 を、A の前から 1 番目の位置になるように挿入する。 A=(4,2,3,1) となる。

入力例 2

5
1 2 3 4 5

出力例 2

1 2 3 4 5

Score : 500 points

Problem Statement

There is an empty array A. For i = 1,2,\ldots,N, perform the following operation in order:

  • Insert the number i into A so that it becomes the P_i-th element from the beginning.
    • More precisely, replace A with the concatenation of the first P_i-1 elements of A, then i, then the remaining elements of A starting from the P_i-th element, in this order.

Output the final array A after all operations have been completed.

Constraints

  • 1 \leq N \leq 5\times 10^5
  • 1 \leq P_i \leq i
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N

Output

Let the final array be A = (A_1, A_2, \ldots, A_N). Print A_1, A_2, \ldots, A_N in this order, separated by spaces.

Sample Input 1

4
1 1 2 1

Sample Output 1

4 2 3 1

The operations are performed as follows:

  • Insert the number 1 so that it becomes the 1st element of A. Now, A = (1).
  • Insert the number 2 so that it becomes the 1st element of A. Now, A = (2, 1).
  • Insert the number 3 so that it becomes the 2nd element of A. Now, A = (2, 3, 1).
  • Insert the number 4 so that it becomes the 1st element of A. Now, A = (4, 2, 3, 1).

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1 2 3 4 5