The Most Mobile - 2
When numbers are sorted lexicographically, their order might differ from their order by numerical value. For instance, while numerically 15 is less than 123, lexicographically 123 precedes 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 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.
Input
The first line contains the integer N, followed by N integers (1 ≤ N ≤ 250000, with absolute values not exceeding 10^18. The numbers may not all be distinct.).
Output
Output a single line with the solution to the problem.