Вам даны n чисел a1, a2, ..., an. Найдите наименьшее целое положительное число x, не содержащееся в множестве {a1, ..., an}, то есть, такое, что не существует i, для которого верно ai = x.

В первой строке записано целое число n (1 ≤ n ≤ 10⁵) — количество чисел. Во второй строке через пробел записаны n чисел: a1, ..., an (1 ≤ ai ≤ 10⁹).

Выведите наименьшее целое положительное x не содержащееся в множестве {a1, ..., an}.

Входные данные

5
1 2 3 4 5

6

5
1 3 4 5 6

2

Тесты разделены на группы, но оцениваются отдельно

• n = 1 — 10 баллов
• n ≤ 100 — 20 баллов
• ai ≤ 10⁶ — 30 баллов
• Без дополнительных ограничений.

Так, если вы решили задачу для n ≤ 100, то вы получите 30 баллов за первую и вторую группы, если вы решили задачу для a_i ≤ 10⁶, то вы получите 30 баллов за третью группу. Если ваша программа будет работать в обоих случаях, то вы получите 60 баллов. За полное решение вы получите 100 баллов.

Загруженные файлы:

Примечание учителя: