320. Smallest Missing Positive

Core1000 ms256 MBSolved by 0%

Print the smallest positive integer that does NOT appear in the array.

1 2 0 -> 3 3 4 -1 1 -> 2 7 8 9 -> 1

Positive means 1 or greater, so zero and negatives are simply irrelevant and the answer is never below 1.

Put everything in a set and try 1, 2, 3 upwards until one is missing. That terminates quickly: with n values present, the answer can never exceed n + 1, so at most n + 1 lookups happen however large the values are.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`

Input

The first line contains an integer n. The second line contains n integers.

Output

Print one integer, the smallest positive integer absent from the array.

Input3 1 2 0

Output3

Notehas a zero that must be ignored rather than counted

Input4 3 4 -1 1

Output2

Notehas the answer in a gap among the present values

Input3 7 8 9

Output1

Notehas no small values at all, so the answer is 1

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution