Послідовність Леді#10495

Послідовність Леді

1 секунда

256 мегабайтів

Складна

Леді записала на листочку послідовність з $k$ послідовних додатних цілих чисел. Перше число було рівне $n$ (наприклад, якщо $n = 47$ n = 47, а $k = 5$ k = 5, то послідовність мала вигляд $[47, 48, 49, 50, 51]$ [47, 48, 49, 50, 51]). Коли вона пішла в школу, її молодша сестра вирішила погратись з послідовністю і видалила з кожного числа усі цифри, окрім однієї. Таким чином утворилась послідовність з $k$ цифр.

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

Вхідні дані

Перший рядок містить одне ціле число $k$ ( $1 \leq k \leq 1 0^{5}$ 1 \leq k \leq 10^5) — кількість чисел в послідовності.

Другий рядок містить $k$ цифр $b_{1}, b_{2}, \dots, b_{k}$ b_1, b_2, \dots, b_k ( $0 \leq b_{i} \leq 9$ 0 \leq b_i \leq 9) — послідовність цифр, яку побачила Леді після повернення зі школи.

Вихідні дані

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

Приклади

Приклад 1

Примітка

$n = 47$ n = 47 дає послідовність $[47, 48, 49, 50, 51, 52]$ [47, 48, 49, 50, 51, 52], з якої молодша сестра Леді могла вилучити цифри і отримати послідовність цифр з прикладу. Оскільки ніякі менші значення $n$ не підійдуть, відповідь $47$ .

Оцінювання

( $9$ балів): $1 \leq k \leq 1000$ 1 \leq k \leq 1000, правильна відповідь не перевищує $1000$ ;
( $33$ бали): $1 \leq k \leq 1000$ 1 \leq k \leq 1000;
( $25$ балів): $1 \leq k \leq 1 0^{5}$ 1 \leq k \leq 10^5, усі цифри послідовності рівні;
( $33$ бали): $1 \leq k \leq 1 0^{5}$ 1 \leq k \leq 10^5.