만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

수열에 나타나지 않는 가장 작은 수

면접 대비

시간 제한1초메모리 제한256 MB

요약
최대 1000개 숫자에서 연속된 구간으로 나타나지 않는 가장 작은 음이 아닌 정수를 구합니다.
난이도

보통10점 중 4점

유형
문자열 매칭, 완전 탐색
정답자
아직 제출이 없습니다

문제

하나코는 음이 아닌 정수를 아무거나 하나 고르면 그 수가 원주율 π=3.14159265…\pi = 3.14159265\ldots 의 어딘가에 반드시 나타난다는 이야기를 들었다. 그 뒤로 하나코는 숫자가 나열된 수열을 보면 그 수열에 어떤 정수가 나타나는지 세어 보게 되었다.

수열에 나타나는 정수는 연속한 몇 개의 숫자를 순서대로 이어 붙여 십진수로 읽은 값이다. 두 자리 이상인 값은 맨 앞 숫자가 0이면 안 된다. 예를 들어 수열 3 0 1에 나타나는 정수는 3, 0, 1, 30, 301로 모두 다섯 가지다.

하나코가 알고 싶은 것은 주어진 수열에 나타나지 않는 가장 작은 음이 아닌 정수다. 위 수열에는 0과 1이 나타나지만 2는 나타나지 않으므로 답은 2다.

하나코의 궁금증을 풀어 줄 프로그램을 작성하라.

입력

첫째 줄에 수열의 길이 NN (1≤N≤10001 \le N \le 1000)이 주어진다.

둘째 줄부터 D1,D2,…,DND_1, D_2, \ldots, D_N이 순서대로 주어진다. 각 DkD_k는 0 이상 9 이하의 정수이고, 이웃한 두 숫자 사이는 공백이나 줄바꿈으로 구분된다.

출력

주어진 수열에 나타나지 않는 가장 작은 음이 아닌 정수를 한 줄에 출력한다.

예제6

  1. 예제 1

    입력
    3
    3 0 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    11
    9 8 7 6 5 4 3 2 1 1 0
    
    예상 출력
    12
    
  3. 예제 3

    입력
    10
    9 0 8 7 6 5 4 3 2 1
    
    예상 출력
    10
    
  4. 예제 4

    입력
    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
    
    예상 출력
    11
    
  5. 예제 5

    입력
    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
    
    예상 출력
    86
    
  6. 예제 6

    입력
    1
    3
    
    예상 출력
    0