First Missing Positive

You are given an unsorted integer array. Your task is to find the smallest missing positive integer from the array. In other words, you need to determine the smallest positive integer that does not appear in the array.

Your solution must run in O(n) time and use constant extra space.

Note: The input will be read from standard input (stdin) and the result must be printed to standard output (stdout).

Example:
For the input array: [1, 2, 0], the smallest missing positive integer is 3.

inputFormat

The first line of input contains an integer n representing the number of elements in the array.
The second line contains n space-separated integers which represent the elements of the array.

outputFormat

Output a single integer – the smallest missing positive integer from the array.

3
1 2 0

3