Задача: Отсутствующее число
Вам даны n чисел a1, a2, ..., an. Найдите наименьшее целое положительное число x, не содержащееся в множестве {a1, ..., an}, то есть, такое, что не существует i, для которого верно ai = x.
Входные данные
В первой строке записано целое число n (1 ≤ n ≤ 105) — количество чисел. Во второй строке через пробел записаны n чисел: a1, ..., an (1 ≤ ai ≤ 109).
Выходные данные
Выведите наименьшее целое положительное x не содержащееся в множестве {a1, ..., an}.
Примеры тестов
Входные данные
Входные данные
5
1 3 4 5 6
Примечание
Тесты разделены на группы, но оцениваются отдельно
-
n = 1 — 10 баллов
-
n ≤ 100 — 20 баллов
-
ai ≤ 106 — 30 баллов
-
Без дополнительных ограничений.
Так, если вы решили задачу для n ≤ 100, то вы получите 30 баллов за первую и вторую группы, если вы решили задачу для ai ≤ 106, то вы получите 30 баллов за третью группу. Если ваша программа будет работать в обоих случаях, то вы получите 60 баллов. За полное решение вы получите 100 баллов.
Ваш ответ: