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 1000$

The correct answer does not exceed $1000$.

Subtask 2 [33%]

$1\le K\le 1000$

Subtask 3 [25%]

$1\le K\le 100000$

$B_1=B_2=\cdots =B_K$

All elements of the given sequence are equal.

Subtask 4 [33%]

$1\le K\le 100000$

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 $474849505152$ from which Billy's sequence can indeed be obtained. As no smaller value of $N$ would work, the answer is $47$.