Задача 21844. missing number

You are given n numbers a1, a2, ..., an. Find the smallest positive integer x not contained in the set {a1, ..., an}, that is, such that there is no i such that ai = x is true.

The first line contains an integer n (1 ≤ n ≤ 10⁵) — amount of numbers. The second line contains n space-separated numbers: a1, ..., an (1 ≤ ai ≤ 10⁹).

Print the smallest positive integer x not contained in the set {a1, ..., an}.

Input

5
1 2 3 4 5

6

5
1 3 4 5 6

2

Tests are divided into groups, but scored separately

• n = 1 — 10 points
• n ≤ 100 — 20 points
• ai ≤ 10⁶ — 30 points
• No additional restrictions.

So, if you solved the problem for n ≤ 100, then you will get 30 points for the first and second groups, if you solved the problem for a_i ≤ 10 ⁶, you will get 30 points for the third group. If your program works in both cases, then you will get 60 points. You will receive 100 points for a complete solution.