Livefree likes trees very much. More importantly he likes binary trees. One day his friend Aldehyde came in his room and gave him some numbers and asked him to add into a binary search tree and traverse the tree in the zig-zag order.(Zig-zag order means traverse one level of tree from left to right and then next level right to left). His friend also told him that the level that contains the root of the tree i.e. the level 1 must be traversed from left to right. Now Livefree is in a hurry to go home so he asked your help. Help him :P

If the data of two nodes are same then the node is not inserted. :P

Input:

The first line of input contains the number of nodes that are to be inserted into the tree. The next n lines contains the data of the node.

Output

The output contains a single line having the zig-zag traversal of the tree.

Constraints

1<=n<=1000

0<=data of each node<= 100000000