Smallest Missing Positive Integer

You are given an array of integers. Your task is to find the smallest positive integer (greater than 0) that does not occur in the array.

Details:

• The array can contain both positive and negative integers, as well as duplicates.
• You should implement an efficient algorithm to determine the smallest missing positive integer.

Examples:

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

Note: If all integers from 1 to n (where n is the size of the array) exist in the array, then the answer is \(n+1\). The algorithm should ideally run in O(n) time and use constant extra space.

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.

Example Input:

5
3 4 -1 1 0

outputFormat

Output a single integer, which is the smallest positive integer that is missing from the input array.

Example Output:

2

## sample

5
3 4 -1 1 0

2