Последовательность Леди

Леди записала на листке последовательность из $k$ последовательных положительных целых чисел, начиная с числа $n$. Например, если $n=47$ и $k=5$, то последовательность выглядела как $[47,48,49,50,51]$. Пока Леди была в школе, её младшая сестра решила поиграть с этой последовательностью и удалила из каждого числа все цифры, кроме одной. В результате получилась последовательность из $k$ цифр.

Когда Леди вернулась из школы, она была очень расстроена, так как хотела восстановить свою последовательность, но забыла число $n$. Ваша задача — помочь Леди и найти наименьшее возможное $n$, с которого могла начинаться эта последовательность.

Входные данные

Первая строка содержит одно целое число $k$ ($1\le k\le 10^5$) — количество чисел в последовательности.

Вторая строка содержит $k$ цифр $b_1,b_2,\dots ,b_k$ ($0\le b_i\le 9$) — последовательность цифр, которую увидела Леди после возвращения из школы.

Выходные данные

Выведите в единственной строке наименьшее число $n$, с которого могла начинаться последовательность Леди.

Примеры

Примечание

Например, $n=47$ даёт последовательность $[47,48,49,50,51,52]$, из которой младшая сестра Леди могла удалить цифры, чтобы получить последовательность цифр из примера. Поскольку никакое меньшее значение $n$ не подходит, ответ — $47$.

Оценивание

1. ($9$ баллов): $1\le k\le 1000$, правильный ответ не превышает $1000$;

2. ($33$ балла): $1\le k\le 1000$;

3. ($25$ баллов): $1\le k\le 10^5$, все цифры последовательности одинаковы;

4. ($33$ балла): $1\le k\le 10^5$.