Problem Statement

Skew heaps are an excellent implementation of priority queues. A skew heap is a binary tree like a binary search tree, but with a different ordering of its elements. In a skew heap, the elements are heap-ordered, meaning that every child is larger than its parent. A left sibling is not required to be smaller than its right sibling, and skew heaps are not required to be balanced. The heap-ordering property implies that the minimum element in a skew heap is always the root.

Inserting a new element X into a skew heap H is done recursively. The base case applies when H is empty or when X is smaller than the existing root. The new element becomes the new root, with the old root as its left child. The recursive case applies when X is larger than the existing root. The left and right subtrees of the existing root are swapped, and X is inserted recursively into the left subtree (which was the right subtree before the swap). These two cases are illustrated below.

     BASE CASE (H is empty or X < root of H)
     ---------------------------------------
       Insert(X, H) ===>   X
                          /
                         H

     RECURSIVE CASE (X > Y)
     ---------------------------------------
       Insert(X,  Y  ) ===>            Y
                 / \                  / \
                A   B       Insert(X,B)  A

The following snapshots show the results of sequentially inserting the numbers 0,1,2,3,4,5,6 into an initially empty tree (where all children not shown are assumed to be null):

      0    0    0        0        0         0           0
          /    / \      / \      / \       / \         / \
         1    2   1    1   2    2   1     /   \       /   \
                      /        /   /     1     2     2     1
                     3        4   3     / \   /     / \   / \
                                       5   3 4     6   4 5   3

On the other hand, it is also possible to get an unbalanced tree if the elements are not inserted in sorted order. For example, sequentially inserting the numbers 6,4,5,2,0,1,3 into an initially empty tree yields

      6    4    4        2        0     0         0
          /    / \      /        /     / \       / \
         6    5   6    4        2     1   2     2   1
                      / \      /         /     / \
                     5   6    4         4     3   4
                             / \       / \       / \
                            5   6     5   6     5   6

Your task is to write a method that will take a skew heap and return the sequence of insertions that might have created that heap. If more than one sequence of insertions might have created the final skew heap, return the lexicographically earliest. A sequence A is lexicographically earlier than a sequence B if the element of A at the leftmost position at which the sequences differ is smaller than the element of B at the same position.

The input heap contains the values 0 through n-1, inclusive, where n is the size of the heap. Each value appears exactly once in the heap. The shape of the input tree will be represented by a int[], parent, of size n-1. If the node containing i is a left child, then element i-1 of parent is the value of the node's parent. If the node containing i is a right child, then element i-1 of parent is 100 plus the value of the parent. Note that parent is 0-indexed. The node containing 0 is always the root, so its parent is not represented. For example, the skew heap

              0
             / \
            1   2
           /   / \
          5   4   3

• 1 is the left child of 0.
• 2 is the right child of 0.
• 3 is the right child of 2.
• 4 is the left child of 2.
• 5 is the left child of 1.

No skew heap built entirely by inserts will ever contain a node with an empty left subtree and a non-empty right subtree. Such heaps will not be permitted as input.

Definition

Constraints

Examples