Thinking Heap

A binary heap is one way to implement a heap, and it is built as a complete binary tree. A complete binary tree is a kind of binary tree in which every level except the last is full, and the nodes on the last level are packed to the left.

<그림> Example of a complete binary tree

A complete binary tree is easy to implement with a one-dimensional array. Number each node as shown below and use that number as the index into the array.

<그림> Complete binary tree with numbered nodes

With this layout, the insertion algorithm for a binary min-heap is simple to implement. The code below implements the insertion algorithm in C++. Small issues in the code are ignored. Calling the insert_heap() function inserts an element into the binary min-heap correctly.

<그림> Code implementing the algorithm that inserts an element into a binary min-heap

Start with an empty binary min-heap. Insert $N$ distinct natural numbers from 1 to $N$ inclusive, one at a time with the insert_heap() function. After all $N$ numbers are inserted, find an insertion order that places the number $k$ at position $p$ of the heap array. Count the first cell of the array as position 0.

The first line contains a natural number $N$ ($1 \le N \le 200,000$). The second line contains two natural numbers $k$ and $p$ ($1 \le k, p \le N$), separated by a space.

If an insertion order exists that places $k$ at position $p$ of the heap array, print the number to insert on each line, with the $i$-th line holding the $i$-th number to insert. If several orders are possible, print any one of them. If no such order exists, print -1 on the first line.