Найрухоміший#5891

Найрухоміший

2 секунди

64 мегабайти

Легка

Як відомо, якщо впорядкувати числа лексикографічно, їх порядок може відрізнятися від порядку за зростанням. Наприклад, $15 < 123$ 15 < 123, але лексикографічно $123$ розташовується перед $15$ . Нагадаємо, що при лексикографічному порівнянні відбувається посимвольне порівняння записів чисел зліва направо (тобто ці записи порівнюються як рядки).

Для заданих $N$ цілих чисел потрібно визначити число, яке може займати найбільш різні позиції в обох згаданих впорядкуваннях. Якщо є кілька таких чисел, виберіть найменше з них.

Вхідні дані

У першому рядку задано число $N$ , а в наступному рядку — $N$ цілих чисел ( $1 \leq N \leq 250000$ 1 \le N \le 250000, абсолютне значення чисел не перевищує $1 0^{18}$ 10^{18}).

Вихідні дані

Виведіть в єдиному рядку відповідь на задачу.

Приклади

Приклад 1