#H499. Cartesian Tree

Cartesian Tree

题目描述

ACartesian treeis a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure.

1.jpg

Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.

输入格式

Each input file contains one test case. Each case starts from giving a positive integerN(≤30), and thenNdistinct numbers in the next line, separated by a space. All the numbers are in the range ofint.

输出格式

For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.

10
8 15 3 4 1 5 12 10 18 6

1 3 5 8 4 6 15 10 12 18