Find Missing Positive Integer

Given an unsorted array of integers, your task is to find the smallest positive integer \(x\) that does not appear in the array.

You are required to implement an algorithm with a time complexity of \(O(n)\) and constant extra space \(O(1)\) (not counting the input array). This means you should rearrange the array in-place as needed.

For example, if the input array is [3, 4, -1, 1], the smallest missing positive integer is 2.

inputFormat

The input is read from stdin. The first line contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

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

4
3 4 -1 1

2