Anshul loves to play with arrays a lot. As a part of new year's resolution, she has to solve a problem on array every 3 days. But the problem is that she is never able to solve the questions correclty. She usually asks her friend Namrta to help her in solving the problems. But this time Namrta is out of town and couldn't solve Anshul's problem. Anshul is very tensed and is hoping for your help to solve the question. She has got an array and for every element present in the array, she wants to print the greater element next to every element. The greater element which is next for an element p is the first bigger element on the right side of p in that array. If there are elements for which there exist no greater element on the right side, consider the greater element next to those elements as -1.

Suppose Anshul has an array [9, 11, 5, 99], following list contains the next greater elements for each element in the array in the format: Element and NextGreaterElement with 2 spaces separation in between:

9  11

11  99

5  99

99  -1

For another array [49, 8, 5, 28], the output list:

49  -1

8  28

5  28

28  -1

Input Format

The first line of input contains an integer n denoting the size of the array

The next line contains n space seperated array elements in integer range

0 < n < = 65500

Output Format

Output consists of n lines

Each line should contain 2 space seperated integers

The first integer should represent the array element and second integer should represent the next greater element

Sample Input

4

4 5 2 25

Sample Output

4 5

5 25

2 25

25 -1