카드 묶음
시간 제한2초메모리 제한128 MB
1부터 N까지 섞인 카드 배열에서 인접한 묶음들을 연속된 정수 묶음이 되도록 합쳐 하나로 만드는 N-1번의 병합 순서를 출력하는 문제입니다.
문제
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를 출력한다.