Informatica Online Judge

  Strange Binary Tree (Small) [1671 / 0687]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 66   Total Tried : 175


The Champion of this Problem (C++) : gs14092 - ms / 255byte
My Best Submission (C++) : N/A

[JKJeong 2016]

Background

BST(Binary Search Tree)란 이진트리로 자료가 입력되는 순서대로 탐색을 할 수 있는 트리의 형태를 구성한다.

예를 들어 $3, 1, 2, 4$의 순서대로 입력이 된다면, 처음 입력되는 3을 루트로 하는 트리를 만들고, $1$은 $3$보다 작으니까 $3$의 왼쪽 노드가 된다.

계속해서 $2$는 $3$보다 작으니 $3$의 왼쪽으로 탐색하고 $2$보다는 크니까 다시 2의 오른쪽 노드가 된다. 이러한 과정을 그림으로 나타내면 다음과 같다.




그리고 BST를 중위순회를 하면 $1, 2, 3, 4$의 순으로 오름차순의 결과를 얻을 수 있다.

그러나 경곽이는 BST을 잘못이해하여 다음과 같은 트리를 만들었다.

먼저 처음 입력되는 값을 루트로 한다. 다음부터 각 값은 마지막으로 생성된 노드보다 크면 마지막 노드 오른쪽에, 아니면 마지막 노드 왼쪽에 삽입하도록 프로그램을 작성했다. ㅠㅠ

예를 들어 $3, 1, 2, 4$와 같은 순서는 다음 그림과 같이 구성된다.



경곽이가 만든 조금 이상한 BST를 만들고 그 트리를 중위순회한 결과를 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 노드의 수를 나타내는 자연수 $n$이 입력된다.

두 번째 줄에 $1$부터 $n$까지의 수로 구성된 하나의 순열이 공백으로 구분되어 입력된다.

[입력값의 정의역]

$2 \leq n \leq 100$

Output

이상한 BST의 중위순회 결과를 출력한다.

IO Example

입력
4
3 1 2 4

출력
1 2 4 3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]