Find the First Missing Positive Integer

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

For example, given the array \( [3, 4, -1, 1] \), the smallest missing positive integer is \(2\). Similarly, for \( [1, 2, 0] \) the answer is \(3\). The solution should run in \(O(n)\) time and use constant extra space \(O(1)\).

Note: The algorithm should only consider positive integers and must read input from the standard input and print the result to the standard output.

inputFormat

The first line contains a single integer \(n\) representing 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 which is the smallest missing positive integer.

4
3 4 -1 1

2