카페의 전달 선반

문제

한 카페는 완성된 음료를 손님에게 전달하기 전에 긴 선반에 한 줄로 놓는다. 바쁜 시간에도 직원마다 같은 순서로 음료를 놓을 수 있도록, 카페는 음료에 기록된 두 값을 이용하는 정리 규칙을 만들었다. 각 음료에는 손님이 찾아오기로 한 시각과 보관 민감도가 적혀 있다. 보관 민감도는 음료를 오래 두었을 때 품질이 달라지기 쉬운 정도를 나타내며, 값이 클수록 먼저 확인해야 한다. 오늘 정리할 음료는 N개다. 음료에는 입력된 순서대로 1번부터 N번까지 서로 다른 번호가 붙는다. 모든 음료는 이미 완성되어 있으며, 직원은 이 음료들을 선반의 왼쪽부터 오른쪽까지 하나씩 배치하려 한다. 선반에는 모든 음료를 놓을 수 있고, 음료를 옮기는 데 걸리는 시간은 고려하지 않는다. 배치할 때는 먼저 손님이 찾아오기로 한 시각을 비교한다. 더 이른 시각의 음료가 반드시 왼쪽에 있어야 한다. 찾아올 시각이 같다면 보관 민감도를 비교하여, 민감도가 더 큰 음료를 왼쪽에 놓는다. 찾아올 시각과 보관 민감도가 모두 같다면 번호가 더 작은 음료를 왼쪽에 놓는다. 이 세 규칙은 적힌 순서대로 적용하며, 앞의 규칙으로 순서를 정할 수 있다면 뒤의 규칙은 사용하지 않는다. 예를 들어 찾아올 시각이 더 이른 음료는 민감도가 작더라도 더 늦은 시각의 음료보다 왼쪽에 놓인다. 반면 찾아올 시각이 같은 두 음료 사이에서는 민감도가 큰 음료를 우선한다. 두 값이 모두 같은 음료도 합치거나 생략하지 않고 각각 선반의 한 자리를 차지한다. 이 작업은 음료를 만드는 순서나 실제로 전달하는 시각을 정하는 작업이 아니다. 주어진 기록만으로 선반에 놓을 순서를 정한다. 위 규칙을 모두 적용했을 때 선반의 가장 왼쪽부터 가장 오른쪽까지 놓이는 음료 번호를 출력하는 프로그램을 작성한다. 마지막 규칙에 사용하는 번호가 모두 다르므로 올바른 배치 순서는 항상 하나로 정해진다.

입력

첫째 줄에 음료 수 N이 주어진다. N은 1 이상 30,000 이하의 정수다.
다음 N개의 줄에 음료의 찾아올 시각 T와 보관 민감도 H가 공백으로 구분되어 주어진다. T와 H는 각각 0 이상 1,000,000,000 이하의 정수다.
이 N개 줄 중 i번째 줄에 주어진 음료의 번호는 i다.

출력

선반의 왼쪽부터 오른쪽까지 놓이는 음료 번호 N개를 공백으로 구분하여 한 줄에 출력한다. 각 번호는 정확히 한 번씩 출력해야 한다.

6
12 4
8 2
12 9
8 7
12 9
15 100

4 2 3 5 1 6

4
0 0
0 0
0 0
0 0

1 2 3 4

1
1000000000 0

1

출처: Devin.KR 자체 제작