7-4 Cartesian Tree (30分)
A Cartesian tree is 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.

Input Specification:
Each input file contains one test case. Each case starts from giving a positive integer N (≤30), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.

Output Specification:
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.

Sample Input:
10
8 15 3 4 1 5 12 10 18 6
Sample Output:
1 3 5 8 4 6 15 10 12 18

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;

const int N = 30 + 10, inf = 214748367;
int q[N], rt;
unordered_map <int, int> pos, L, R;
int build(int l, int r)
{
    int root = inf;
    for(int i = l; i <= r; i ++) root = min(root, q[i]);
    if(pos[root] > l) L[root] = build(l, pos[root] - 1);
    if(pos[root] < r) R[root] = build(pos[root] + 1, r);
    return root;
}


int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) 
    {
        cin >> q[i];
        pos[q[i]] = i;
    }
    rt = build(0, n - 1);

    vector <int> ans;
    queue <int> lev;
    lev.push(rt);
    while(lev.size()) 
    {
        int t = lev.front();
        ans.push_back(t);
        lev.pop();
        if(L.count(t)) lev.push(L[t]);
        if(R.count(t)) lev.push(R[t]);
    }
    cout << ans[0];
    for(int i = 1; i < ans.size(); i ++) cout << ' ' << ans[i];
    return 0;
}