Thinking Heap

Binary heap은 Heap을 구현하는 방법 중 하나로, Complete binary tree 형태로 만들어진다. Complete binary tree는 Binary tree의 한 종류이다. 마지막 레벨을 제외한 모든 레벨의 노드가 꽉 차 있고, 마지막 레벨의 노드는 왼쪽으로 몰려 있다.

<그림> Complete binary tree의 예

Complete binary tree는 1차원 배열을 이용하면 쉽게 구현할 수 있다. 각 노드에 아래 그림과 같이 번호를 붙이고, 그 번호를 1차원 배열의 index로 쓰면 된다.

<그림> 번호를 붙인 Complete binary tree

이 방식을 쓰면 Binary min-heap에 원소를 삽입하는 알고리즘을 간단히 구현할 수 있다. 아래 코드는 삽입 알고리즘을 C++로 구현한 것이다(코드의 자잘한 문제들은 신경 쓰지 않는다). insert_heap() 함수를 호출하면 Binary min-heap에 원소가 알맞게 삽입된다.

<그림> Binary min-heap에 원소를 삽입하는 알고리즘을 구현한 코드

비어 있는 Binary min-heap에 1 이상 $N$ 이하의 서로 다른 자연수 $N$개를 insert_heap() 함수로 삽입한다. $N$개를 모두 삽입한 뒤, 자연수 $k$가 heap 배열의 $p$번째 칸에 위치하도록 하는 삽입 순서를 찾는 프로그램을 작성하시오. 배열의 맨 처음 칸은 0번째로 센다.

첫 번째 줄에 자연수 $N$ ($1 \le N \le 200,000$)이 주어진다. 두 번째 줄에 자연수 $k$와 $p$ ($1 \le k, p \le N$)가 공백으로 구분되어 주어진다.

$k$가 heap 배열의 $p$번째에 위치하도록 하는 삽입 순서가 존재하면, $i$번째 줄에 $i$번째로 삽입할 수를 출력한다. 가능한 삽입 순서가 여러 개라면 그중 아무거나 하나를 출력해도 된다. 그런 삽입 순서가 존재하지 않으면 첫 번째 줄에 -1을 출력한다.