题目描述

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.

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

笛卡尔树 是由一系列不同数字构成的二叉树。树满足堆的性质，中序遍历返回原始序列。最小笛卡尔树表示满足小根堆性质的笛卡尔树。例如，给定序列 {8,15,3,4,1,5,12,10,18,6}，则生成的最小堆笛卡尔树如图所示。

现在，给定一个长度为 N 的原始序列，请你生成最小堆笛卡尔树，并输出其层序遍历序列。

输入格式

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.

第一行包含整数 N。（1≤N≤30 ,原始序列中元素的取值范围 [−2147483648,2147483647]。

第二行包含 N 个两两不同的整数，表示原始序列。

输出格式

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