First Missing Positive

You are given an unsorted array A of N integers. Your task is to find the smallest missing positive integer.

For example, if A = [3, 4, -1, 1, 2], the smallest missing positive integer is 5. In mathematical terms, you need to find the minimum positive integer m such that:

$$ m \notin \{A_1, A_2, \dots, A_N\} $$

Please note that the array may contain negative numbers and zeros. Your solution should run efficiently in O(N) time.

inputFormat

The input is given via stdin and consists of two lines:

• The first line contains an integer N which represents the number of elements in the array.
• The second line contains N space-separated integers, representing the elements of the array.

outputFormat

Output a single integer to stdout which is the smallest missing positive integer from the array.

5
3 4 -1 1 2

5