시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3161067237.500%

문제

1 이상 N 이하의 자연수가 한 장에 하나씩 순서대로 적혀 있는 N장의 카드가 있다. 이 카드를 임의의 순서로 섞은 뒤 일렬로 배열하였다. 아래는 N = 6인 경우의 한 예이다.

[6] [3] [2] [1] [4] [5]

각각 N장의 카드는 하나의 묶음을 이루고 있다고 생각할 수 있다. 즉 초기에 N개의 카드 묶음이 순서대로 배열되어 있는 것이다.

만일 하나의 카드 묶음 속에 포함되어 있는 카드들이 서로 연속된 수들로만 이루어져 있으면, 그러한 묶음을 유효한 카드 묶음이라고 한다. [2], [4 5], [3 5 6 4] 등은 유효한 카드 묶음의 예이다.

인접한 두 개의 카드 묶음을 하나로 합쳤을 때 새로 생긴 카드 묶음도 유효한 카드 묶음이면, 두 카드 묶음을 하나로 합칠 수 있다. 이러한 과정을 N-1번 반복하면 N개의 카드를 하나의 카드 묶음으로 만들 수 있다. 아래는 이러한 과정의 한 예를 순서대로 보인 것이다.

[6] [3] [2] [1] [4] [5]
[6] [3] [2 1] [4] [5]
[6] [3 2 1] [4] [5]
[6] [3 2 1] [4 5]
[6] [3 2 1 4 5]
[6 3 2 1 4 5]

N장의 카드의 초기 배열이 주어졌을 때, 이러한 과정을 N-1번 반복하여 N개의 카드를 하나의 카드 묶음으로 만드는 과정을 구하는 프로그램을 작성하시오. 항상 가능한 경우만이 입력으로 주어지며, 여러 가지 해 중에서 하나만 출력하면 된다.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 카드의 초기 배열을 나타내는 N개의 정수가 빈 칸을 사이에 두고 순서대로 주어진다.

출력

첫째 줄부터 N-1개 줄에 걸쳐 합치는 과정을 표현해 줄 한 개의 정수를 출력한다. 합쳐질 두 개의 묶음 중, 앞 묶음의 마지막 카드가 몇 번째 카드인지를 출력하면 된다. 예를 들어, [6] [3 2 1] [4 5]의 경우, 앞 묶음인 [3 2 1]의 마지막 카드인 1은 네 번째이므로, 4를 출력하면 된다.

예제 입력 1

6
6 3 2 1 4 5

예제 출력 1

3
2
5
4
1

출처

  • 문제를 번역한 사람: author5