Search Tree

Problem code: HS11BST

A sequence of n integers has been inserted into a binary search tree (before the operation the tree was empty). The tree stores unique elements, only, and all duplicates are simply ignored.

Please print in ascending order all the tree elements whose depth is equal to h-1, where h is the height of the tree.

Input

First n (2<=n<=100000) - the number of integers in the sequence. In the next n lines the sequence of integers, one integer x_i (-1000000 < x_i < 1000000) in each line. You can assume that the height of the tree will be at least 1.

Output

The requested integers, one integer in each line.

Example

Input:
8
3
1
8
5
3
12
9
8

Output:
5
12

Scoring

By solving this problem you score 10 points.