eolymp
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