The most agile

When numbers are sorted lexicographically, their order may differ from their order by numerical value. For instance, while 15 is less than 123 numerically, lexicographically 123 comes before 15. This is because lexicographic comparison treats numbers as strings, comparing them character by character from left to right.

Given N integers, identify the number that has the greatest difference in position between these two types of orderings. If there is a tie, choose the smaller number.

Input

The first line contains the integer N, followed by N integers on the next line (1 ≤ N ≤ 250000, with absolute values not exceeding 10^18).

Output

Output a single line with the number that satisfies the problem's conditions.

Examples