Baltic Olympiad in Informatics: 2014 Day 1, Problem 3

Adam wrote down a sequence of ~K~ consecutive positive integers starting with ~N~ on a blackboard. When he left, Billy came in and erased all but one digit from each number, thus creating a sequence of ~K~ digits.

Given the final sequence left on the blackboard, find the smallest value of ~N~ with which the initial sequence might have started.

Constraints

Subtask 1 [9%]

~1 \le K \le 1\,000~

The correct answer does not exceed ~1\,000~.

Subtask 2 [33%]

~1 \le K \le 1\,000~

Subtask 3 [25%]

~1 \le K \le 100\,000~

~B_1 = B_2 = \dots = B_K~

All elements of the given sequence are equal.

Subtask 4 [33%]

~1 \le K \le 100\,000~

Input Specification

The first line of the input contains a single integer ~K~ — the length of the sequence. The second line contains ~K~ space-separated integers ~B_1, B_2, \dots, B_K~ — Billy's sequence ~(0 \le B_i \le 9)~, in the order in which it is written on the blackboard.

Output Specification

The output should consist of a single line with the smallest value of ~N~ with which the initial sequence might have started.

Sample Input

6
7 8 9 5 1 2

Sample Output

47

Explanation for Sample

~N = 47~ would correspond to Adam's sequence being ~47\ 48\ 49\ 50\ 51\ 52~ from which Billy's sequence can indeed be obtained. As no smaller value of ~N~ would work, the answer is ~47~.