Smallest number missing from a digit sequence

Interview

Time limit1sMemory limit256 MB

Summary

Given up to 1000 digits, find the smallest non-negative integer that never occurs as a consecutive block without a leading zero.

Level: Medium4 of 10
Topics: String matching, Brute force
Solved: No attempts yet

Problem

Hanako heard that if you pick any non-negative integer, it always turns up somewhere in the decimal expansion of $\pi = 3.14159265\ldots$ . Since then, whenever she sees a sequence of digits she checks which integers appear in it.

An integer appears in the sequence if you can read it off consecutive digits, in order, as a decimal number. A value of two or more digits must not start with 0. For example, the sequence 3 0 1 contains the integers 3, 0, 1, 30 and 301, five in total.

Hanako wants the smallest non-negative integer that does not appear in the sequence. The sequence above contains 0 and 1 but not 2, so the answer is 2.

Write a program that answers Hanako's question.

Input

The first line contains the length of the sequence $N$ ( $1 \le N \le 1000$ ).

From the second line on, $D_1, D_2, \ldots, D_N$ are given in order. Each $D_k$ is an integer between 0 and 9, and neighbouring digits are separated by a space or a line break.

Output

Print the smallest non-negative integer that does not appear in the sequence.

Examples6

Example 1
Input
```
3
3 0 1
```
Expected output
```
2
```
Example 2
Input
```
11
9 8 7 6 5 4 3 2 1 1 0
```
Expected output
```
12
```
Example 3
Input
```
10
9 0 8 7 6 5 4 3 2 1
```
Expected output
```
10
```

Example 4

Input

100
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2
6 1 8 7 9 2 0 2 3 7 5 9 2 2 8 9 7 3 6
1 2 9 3 1 9 4 7 8 4 5 0 3 6 1 0 6 3 2
0 6 1 5 5 4 7 6 5 6 9 3 7 4 5 2 5 4 7
4 4 3 0 7 8 6 8 8 4 3 1 4 9 2 0 6 8 9
2 6 6 4 9

Expected output

Example 5

Input

100
7 2 7 5 4 7 4 4 5 8 1 5 7 7 0 5 6 2 0
4 3 4 1 1 0 6 1 6 6 2 1 7 9 2 4 6 9 3
6 2 8 0 5 9 7 6 3 1 4 9 1 9 1 2 6 4 2
9 7 8 3 9 5 5 2 3 3 8 4 0 6 8 2 5 5 0
6 7 1 8 5 1 4 8 1 3 7 3 3 5 3 0 6 0 6
5 3 2 2 2

Expected output

Example 6
Input
```
1
3
```
Expected output
```
0
```