User's AC Ratio

86.4% (19/22)

Submission's AC Ratio

56.6% (30/53)

Description

還記得puyo疊疊樂(TIOJ-1193) 嗎

現在我們把滿足puyo疊疊樂性質的二元樹稱為一個「樹狀的堆積結構」:任何非根節點(non-root node)的值都比其父節點(parent node)的數值還要大。

現在給你某棵「樹狀堆積結構」的中序表示法(in-order),請求出它的前序表示法(pre-order)。

※如果你不知道什麼是中序表示法、前序表示法的話,請參考TIOJ-1108

Input Format

輸入檔可能包含不超過1000筆測試資料。
每筆測試資料的第一列有一個正整數n(1<=n<=10,000),代表「堆積樹狀結構」的節點總數。
第二列有n個以空白隔開的正整數,為該「堆積樹狀結構」的中序表示法
你可以假設同一個樹狀堆積結構裡面,不會有相同的正整數,而且所有數字都不會超過109
當n=0的時候代表輸入結束。

Output Format

對於每一筆測試資料,請輸出該「堆積樹狀結構」的前序表示法。

Sample Input

6
3 2 1 5 4 6
0

Sample Output

1 2 3 4 5 6

Hints

1.這種東西好像又叫做笛卡爾樹(Cartesian Tree)!
2.測試資料當中,99%以上的測試資料的n<=1,000。

※2008/02/02輸入說明修正:感謝math120908。

Problem Source

原TIOJ1204 / TIOJ 2008例行賽02 (prob F)。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 65536 262144