ISSPS`13 Wave 2 Day 5
Самый подвижный - 2
Как известно, если числа упорядочить лексикографически, то их порядок может не совпадать с порядком по возрастанию. Например, 15 < 123, но лексикографически 123 располагается раньше, чем 15. Вспомним, что при лексикографическом сравнении происходит посимвольное сравнение записей чисел слева направо (т.е. эти записи сравниваются как строки).
Для заданных N целых чисел определить число, которое может занимать при двух вышеупомянутых упорядочениях наиболее отличающиеся позиции. В равных условиях преимущество дать меньшему числу. Учтите, что равные числа норовят сдвинуться как можно дальше.
Input data
В первой строке число N, в следующей строке N целых чисел (1 ≤ N ≤ 250000, величины чисел по абсолютной величине не превосходят 1018. Не гарантируется, что все числа разные.).
Output data
В единственной строке – ответ задачи.
Examples
3 25 -7 222
25