개미
면접 대비시간 제한2초메모리 제한512 MB
N개의 정수가 주어질 때, 음수와 매우 큰 수는 무시하고 집합에 없는 가장 작은 음이 아닌 정수를 찾는다.
문제
Charles는 개미에 푹 빠져 있다. 개미 군체를 오랫동안 관찰하기 위해 Charles는 이미지 인식을 이용해 각 개미를 고유하게 식별하는 프로그램을 만들었다. (그렇다. 모든 개미는 저마다 다르다.) 프로그램 안에서 각 개미에는 고유한 음이 아닌 정수 태그가 붙는다. 군체에서 새 개미가 태어나면, 이미 부여된 모든 태그와 다른 새 태그가 그 개미에게 주어진다. 어떤 개미가 사라지면 그 태그는 다시 사용 가능한 태그 풀로 돌아간다.
Charles의 프로그램은 다음과 같이 동작한다. 먼저 군체 전체를 스캔해 인식된 개미들의 태그 목록을 만든다. 그다음 새 개미들에게 새 태그를 부여한다. 이때 프로그램은 현재 어떤 개미에게도 배정되지 않은 가장 작은 자연수(즉, 음이 아닌 정수)를 고르고, 그다음에도 마찬가지로 반복한다.
이미지 인식 장치와 프로그램의 결함 때문에 입력 목록에 음수나 아주 큰 수가 나타나기도 한다. Charles의 프로그램은 이런 수를 그냥 무시한다.
여러분의 임무는 새 개미에게 부여할 새 태그를 찾는 부분을 다시 구현하는 것이다.
입력
입력은 다음 줄들로 이루어진다.
- 첫째 줄: 정수 N
- 다음 N개 줄: 정수 X1, ..., XN이 한 줄에 하나씩 주어진다.
출력
집합 {X1, ..., XN}에 속하지 않는 가장 작은 자연수를 출력한다.
제한
입력은 0 ≤ N ≤ 106을 만족한다. 각 정수 Xi는 100자리 미만이다.