You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

題目描述

在遠古時代，先祖們曾以一種特殊的方式記錄他們的族譜。他們以**完全先序遍歷（Preorder Traversal）**的方式寫下整棵二元搜尋樹（Binary Search Tree, BST）的節點值，並以 "null" 字串表示空節點。

如今，考古學家發現了這份紀錄，請你根據這份完全先序遍歷的資料，重建出這棵 BST 並輸出其中序遍歷的結果。

注意：

• 所有節點值互不相同。
• 完全先序遍歷是指不僅包括所有節點，還包括空節點的位置（即原樹結構不變）。
• BST 的定義為：對於每個節點，其左子樹中所有節點的值都小於該節點的值，右子樹中所有節點的值都大於該節點的值。

輸入格式

第一行一個整數 n，表示先序遍歷序列的長度（含 "null" 的項目）。
第二行包含 n 個用空格分隔的字串，代表先序遍歷結果。

• 對於節點值，保證是整數且不重複。
• "null" 表示空節點。

輸出格式

一行，輸出重建後 BST 的中序遍歷結果（僅包含實際節點值，空節點不輸出），用空格分隔。

輸入範例 1

7
5 3 null null 7 null null

輸出範例 1

3 5 7

輸入範例 2

15
10 5 2 null null 7 null null 15 12 null null 20 null null

輸出範例 2

2 5 7 10 12 15 20

數據範圍

• 1 ≤ n ≤ 10^5
• 所有非 "null" 的節點值為整數，絕對值不超過 $10^9$
• 至多有 $2 \times 10^4$ 個 "null"