The Most Mobile - 2#5982
When numbers are sorted lexicographically, their order might differ from their order by numerical value. For instance, while numerically 15 < 123, lexicographically precedes . This is because lexicographic comparison treats numbers as strings, comparing them character by character from left to right.
Given integers, identify the number that can have the most different positions between these two types of orderings. If there is a tie, choose the smaller number. Note that identical numbers should be placed as far apart as possible.
The first line contains the integer . The next line contains integers (1 \le N \le 250000, with absolute values not exceeding 10^{18}. The numbers may not all be distinct.).
Output a single line with the solution to the problem.
Example 1