카드 묶음

1 이상 N 이하의 자연수가 카드 한 장에 하나씩 적힌 N장의 카드가 있다. 이 카드들을 임의의 순서로 섞은 뒤 일렬로 놓았다. N = 6일 때의 한 배열은 다음과 같다.

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

처음에는 카드 한 장이 각각 하나의 묶음을 이룬다. 따라서 처음에는 N개의 카드 묶음이 순서대로 놓여 있다.

한 묶음에 들어 있는 카드 번호들이 모두 연속된 수로만 이루어져 있으면 그 묶음을 유효한 카드 묶음이라고 한다. 예를 들어 [2], [4 5], [3 5 6 4]는 모두 유효한 카드 묶음이다.

서로 인접한 두 카드 묶음을 합쳤을 때 새 묶음도 유효하다면, 그 두 묶음을 하나로 합칠 수 있다. 이 과정을 N - 1번 반복하면 모든 카드를 하나의 묶음으로 만들 수 있다. 아래는 가능한 병합 과정 하나를 순서대로 나타낸 것이다.

[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(1 <= N <= 500,000)이 주어진다.

둘째 줄에는 처음 카드 배열을 나타내는 N개의 정수가 빈칸으로 구분되어 순서대로 주어진다.

첫째 줄부터 N - 1개의 줄에 걸쳐 병합 과정을 나타내는 정수 하나씩을 출력한다.

인접한 두 묶음을 합칠 때, 앞 묶음의 마지막 카드가 처음 배열에서 몇 번째 카드였는지를 출력한다. 예를 들어 [6] [3 2 1] [4 5]에서 앞 묶음 [3 2 1]과 뒤 묶음 [4 5]를 합친다면, 앞 묶음의 마지막 카드 1은 처음 배열의 네 번째 카드이므로 4를 출력한다.