Олимпиада информатика срочно

Порядок во всём

Ограничение по времени: 1,5 секунды
Ограничение по памяти: 256 мегабайт

Вася — очень порядочный мальчик, он любит порядок во всём.

У него в тетради есть столбик натуральных чисел, и он хочет изменить его так, чтобы числа шли по порядку, то есть по неубыванию. При этом Вася, естественно, ничего не хочет зачёркивать, поэтому единственное, что ему остаётся — это дописать цифры в конец некоторых чисел.

Вася хочет, чтобы после дописывания цифр последнее число в списке оказалось наименьшим возможным. Найдите это число.

Формат входных данных

Первая строка входных данных содержит целое число n (2≤n≤3⋅105) — количество чисел в тетрадке у Васи.

Следующие n строк содержат n чисел, записанных в тетрадке, по одному в каждой строке. Все числа натуральные, не превосходящие 109.

Формат выходных данных

Программа должна вывести наименьшее число, которое могло оказаться у Васи в конце списка.

Система оценки

Решения, верно работающие, когда n≤5 и при этом все числа в списке однозначные, будут оцениваться в 10 баллов.
Решения, верно работающие, когда n≤5 и при этом все числа в списке не превосходят 999, будут оцениваться в 20 баллов.
Решения, верно работающие, когда n≤5 без дополнительных ограничений на числа, будут оцениваться в 40 баллов.
Решения, верно работающие, когда n≤1000 без дополнительных ограничений на числа, будут оцениваться в 60 баллов.


Замечание

В первом примере числа уже упорядочены, Васе не нужно ничего дописывать.
Во втором примере Васе можно приписать ко второму числу цифру 3, тогда числа станут равны 13, а значит, будут расположены по неубыванию. При этом 13 — это минимально возможное последнее число.
В третьем примере Вася может, например, получить числа 20, 25, 100. Возможны и другие варианты, но последнее число при любом способе дописывания цифр получится не меньше 100.