e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

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

Леді записала на листочку послідовність з $k$ послідовних додатних цілих чисел. Перше число було рівне $n$ (Наприклад, якщо $n$=47, а $k$=5, то послідовність мала вигляд $[47, 48, 49, 50, 51]$). Коли вона пішла в школу, її молодша сестра вирішила погратись з послідовністю і видалила з кожного числа усі цифри, окрім однієї. Таким чином утворилась послідовність з $k$ цифр. Коли Леді повернулась зі школи, вона дуже засмутилась. Вона дуже хотіла повернути свою послідовність, але, на жаль, забула число $n$. Вам потрібно допомогти Леді й знайти найменше можливе $n$, з якого могла починатись послідовність. \InputFile Перший рядок містить одне ціле число $k$ ($1 \leq k \leq 10^5$)~--- кількість чисел в послідовності. Другий рядок містить $k$ цифр $b_1, b_2, \dots, b_k$ ($0 \leq b_i \leq 9$)~--- послідовність цифр, яку побачила Леді після повернення зі школи. \OutputFile В єдиному рядку виведіть відповідь~--- найменше число $n$, з якого могла починатись послідовність Леді. \Note $n = 47$ дає послідовність $[47, 48, 49, 50, 51, 52]$, з якої молодша сестра Леді могла вилучити цифри і отримати послідовність цифр з прикладу. Оскільки ніякі менші значення $n$ не підійдуть, відповідь $47$. \Scoring \begin{enumerate} \item ($9$ балів): $1 \leq k \leq 1000$, правильна відповідь не перевищує $1000$; \item ($33$ бали): $1 \leq k \leq 1000$; \item ($25$ балів): $1 \leq k \leq 10^5$, усі цифри послідовності рівні; \item ($33$ бали): $1 \leq k \leq 10^5$. \end{enumerate}
Time limit 1 second
Memory limit 256 MiB
Input example #1
6
7 8 9 5 1 2
Output example #1
47
Author Sofia Melnyk