First Missing Positive Integer

Given an unsorted integer array, find the smallest missing positive integer. In other words, find the smallest positive integer that does not appear in the array.

The problem must be solved with an algorithm whose time complexity is linear, i.e., \(O(n)\), and which uses constant extra space.

For example:

• For the input array [3, 4, -1, 1], the smallest missing positive integer is 2.
• For the input array [1, 2, 0], the answer is 3.

You will be given the input from standard input (stdin) and your program should output the result to standard output (stdout).

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array. The next line contains \(n\) space-separated integers representing the elements of the array.

If \(n\) is 0, the array is considered empty.

outputFormat

Output a single integer, which is the smallest missing positive integer.

4
3 4 -1 1

2