Teacher QQ thinks ZzK has great potential for development.Same as same Lin he has rewarded brozen prize of provential ACM.Now he teaches himself data structures to Binary Sort Tree.In order to cooperate with his self-study, he decided to examine himself by asking questions.Now give you N nodes with different keyword values, and ask you to insert a binary sorting tree with an empty tree in order. After each successful insertion, find the corresponding key value of the father node, and if there is no father node, output - 1.
The input contains multiple sets of test data, and each group has two rows of test data. The first row, a digit N (N<=100), represents the number of nodes to be inserted. The second line, N distinct positive integers, denotes the keyword values of the nodes to be inserted sequentially, which do not exceed 10 ^ 8.
Multiple data read in
Output a total of N rows, the key value of the node corresponding to the father node after each node is inserted.
5
2 5 1 3 4
-1
2
2
5
3
Binary Sort Tree, also known as two fork search tree. It can be an empty tree, or a non empty two fork tree with the following characteristics.
1. If the left subtree is not empty, the key value of all nodes in the left subtree is not greater than the key value of the root node;
2. If the right subtree is not empty, the key value of all nodes in the right subtree is not less than the key value of the root node;
3. The left and right subtree itself is a binary sort tree.