Find the First Missing Positive Integer

You are given an unsorted array of integers. Your task is to write an algorithm that finds the smallest missing positive integer.

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

More formally, given an unsorted array \(nums\) of size \(n\), find the smallest positive integer \(x\) such that \(x \notin nums\). For example:

• For \(nums = [1, 3, 6, 4, 1, 2]\), the answer is 5.
• For \(nums = [1, 2, 3]\), the answer is 4.
• For \(nums = [-1, -3]\), the answer is 1.

Note: The algorithm should have a time complexity of \(O(n)\) and should operate in-place with regards to the input array.

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.

Example: For an array with 6 elements, the input might be:

6
1 3 6 4 1 2

outputFormat

Output a single integer representing the smallest missing positive integer.

Example: For the above input, the output should be:

5

## sample

6
1 3 6 4 1 2

5