Find Missing Positive Integer

You are given an unsorted list of n integers. Your task is to find the smallest missing positive integer. In other words, find the smallest integer greater than 0 that does not occur in the array.

The solution must run in O(n) time complexity and use constant extra space. A common approach is to rearrange the array in-place such that each positive integer k (if possible) is placed at index k - 1. After that, the first index where the number is not i + 1 represents the missing positive. If all positions are correct, then the missing integer is n + 1.

For example, if the input array is [3, 4, -1, 1], the answer will be 2 because 2 is the smallest positive number that's not present in the array.

The mathematical formulation can be stated as follows:

Let \(A\) be the input array of length \(n\). Find the smallest positive integer \(x\) such that \(x \notin A\).

inputFormat

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

For example:

4
3 4 -1 1

outputFormat

Output a single integer: the smallest missing positive integer.

For the above input, the output should be:

2

## sample

4
3 4 -1 1

2

</p>