로봇 정렬

체코 공과대학교(Czech Technical University) 건물 깊숙한 곳에는 다양한 재료의 기계적·전기적 성질을 검사하는 실험실들이 있다. 이 문제에서는 그러한 실험실에서 시료(sample)를 다루는 로봇을 위한 소프트웨어를 작성한다.

컨베이어 벨트 위에 재료 시료들이 한 줄로 놓여 있다고 하자. 시료마다 높이가 다른데, 이 때문에 다음 처리 장치에서 문제가 생길 수 있다. 이를 없애기 위해 시료들을 높이의 오름차순으로 정렬해야 한다.

정렬은 기계식 로봇 팔로 수행한다. 로봇 팔은 연속한 임의 개수의 시료를 집어 뒤집을 수 있어서, 집어 든 구간의 순서가 반대로 뒤바뀐다. 즉, 로봇 연산 한 번으로 위치 A부터 B까지의 시료 순서를 뒤집을 수 있다.

시료를 정렬하는 한 가지 방법은 다음과 같다. 먼저 가장 작은 시료의 위치 P1을 찾아 위치 1과 P1 사이를 뒤집으면 가장 작은 시료가 맨 앞으로 온다. 그다음 두 번째로 작은 시료의 위치 P2를 찾아 위치 2와 P2 사이를 뒤집는다. 이어서 세 번째 시료를 같은 방식으로 처리하고, 이런 식으로 마지막 시료까지 계속한다.

예를 들어 시료가 6개 있다고 하자. 가장 작은 시료가 4번째 위치에 있다면 로봇 팔은 앞의 4개를 뒤집는다. 두 번째로 작은 시료가 맨 끝에 있다면 다음 연산은 위치 2–6의 다섯 시료를 뒤집는다. 세 번째 단계에서는 위치 3–4를 뒤집고, 이렇게 계속 진행한다.

이 알고리즘으로 시료를 정렬할 때 필요한 뒤집기 연산의 순서를 구하는 것이 목표다. 높이가 같은 시료가 여러 개라면 그들의 상대적 순서는 보존되어야 한다. 즉, 처음 순서에서 앞에 있던 시료는 최종 순서에서도 같은 높이의 다른 시료들보다 앞에 있어야 한다.

입력은 여러 개의 시나리오로 이루어진다. 각 시나리오는 두 줄로 주어진다. 첫 줄에는 시료의 개수 N이 주어진다 (1 ≤ N ≤ 100 000). 둘째 줄에는 정확히 N개의 양의 정수가 공백으로 구분되어 주어지며, 이는 각 시료의 높이와 처음 놓인 순서를 나타낸다.

마지막 시나리오 다음에는 0 하나만 적힌 줄이 온다.

각 시나리오마다 N개의 정수 P1, P2, …, PN을 공백 하나로 구분하여 한 줄에 출력한다. 여기서 Pi는 i번째 뒤집기 연산을 수행하기 직전에, 정렬 결과에서 i번째에 오는 시료(즉 i번째로 작은 시료이며, 높이가 같으면 처음 순서가 앞선 시료)가 놓여 있는 현재 위치이고 1 ≤ Pi ≤ N을 만족한다.

시료가 이미 올바른 위치 Pi에 있더라도 그 Pi 값을 출력해야 한다. 이는 "Pi와 Pi 사이 구간"(시료 한 개)을 뒤집는다는 뜻이다.