Lady Sequence

The lady wrote down a sequence of $k$ consecutive positive integers on a piece of paper. The first number in this sequence was $n$. For instance, if $n=47$ and $k=5$, the sequence would be $[47,48,49,50,51]$. While she was at school, her younger sister played with the sequence and removed all but one digit from each number, resulting in a sequence of $k$ single digits.

When the lady returned from school, she was upset because she couldn't remember the starting number $n$. Your task is to help her find the smallest possible $n$ from which the sequence could have started.

Input

The first line contains a single integer $k$ ($1\le k\le 10^5$) — the number of numbers in the sequence.

The second line contains $k$ digits $b_1,b_2,\dots ,b_k$ ($0\le b_i\le 9$) — the sequence of digits that the lady found when she returned from school.

Output

Output a single line with the answer — the smallest number $n$ from which the lady's sequence could have started.

Examples

Note

For example, $n=47$ results in the sequence $[47,48,49,50,51,52]$, from which the lady's younger sister could have removed digits to create the sequence of digits given in the example. Since no smaller $n$ will work, the answer is $47$.

Scoring

1. ($9$ points): $1\le k\le 1000$, the correct answer does not exceed $1000$;

2. ($33$ points): $1\le k\le 1000$;

3. ($25$ points): $1\le k\le 10^5$, all digits in the sequence are the same;

4. ($33$ points): $1\le k\le 10^5$.