Вася — очень порядочный мальчик, он любит порядок во всём.
У него в тетради есть столбик натуральных чисел, и он хочет изменить его так, чтобы числа шли по порядку, то есть по неубыванию. При этом Вася, естественно, ничего не хочет зачёркивать, поэтому единственное, что ему остаётся — это дописать цифры в конец некоторых чисел.
Вася хочет, чтобы после дописывания цифр последнее число в списке оказалось наименьшим возможным. Найдите это число.
Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(2 \le n \le 3 \cdot 10^{5}\)) — количество чисел в тетрадке у Васи.
Следующие \(n\) строк содержат \(n\) чисел, записанных в тетрадке, по одному в каждой строке. Все числа натуральные, не превосходящие \(10^9\).
Формат выходных данных
Программа должна вывести наименьшее число, которое могло оказаться у Васи в конце списка.
Примечание
В первом примере числа уже упорядочены, Васе не нужно ничего дописывать.
Во втором примере Васе можно приписать ко второму числу цифру 3, тогда числа станут равны 13, а значит, будут расположены по неубыванию. При этом 13 — это минимально возможное последнее число.
В третьем примере Вася может, например, получить числа 20, 25, 100. Возможны и другие варианты, но последнее число при любом способе дописывания цифр получится не меньше 100.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
5
7
|
7
|
|
2
|
2
13
1
|
13
|
|
3
|
3
20
2
1
|
100
|