야바위2 (Stone Arranging 2) timer 2초 memory 1024MB

JOI 군은 N개의 바둑돌을 가지고 있습니다. 각각의 바둑돌에는 1부터 N까지의 번호가 매겨져 있으며, 각 바둑돌은 1 이상 10^9 이하의 정수로 표현되는 색상으로 칠해져 있습니다. 처음에 바둑돌 i(1 ≦ i ≦ N)의 색상은 A_i입니다.

JOI 군은 이제 N번의 작업을 수행하여 바둑돌을 테이블 위에 한 줄로 배치하려고 합니다. i 번째 라운드 (1 ≦ i ≦ N)의 작업은 다음과 같은 단계로 수행됩니다:

1. 바둑돌 i를 바둑돌 {i-1}의 오른쪽에 놓습니다. 그러나 i = 1인 경우에는 바둑돌 1을 테이블 위에 놓습니다.

2. 1, 2, ..., i-1 중 현재 바둑돌 i와 같은 색상을 가진 바둑돌이 있는 경우, 그 중 번호가 가장 큰 바둑돌을 j라고 합니다. 바둑돌 j + 1, j + 2, ..., i - 1의 색상을 모두 색상 A_i로 다시 칠합니다.

작업이 올바르게 수행되었는지 확인하기 위해 JOI 군은 모든 작업을 완료한 후의 모든 바둑돌의 색상을 미리 알고 싶어합니다.

바둑돌에 대한 정보가 주어졌을 때, N번의 작업을 모두 수행한 후 각 바둑돌의 색상을 출력하는 프로그램을 작성하십시오.