Smallest Missing Positive Integer

Given an unsorted array of integers, your task is to find the smallest positive integer that is missing from the array. The array can contain both positive and negative numbers and its size can be up to $10^6$.

Details:

• The input list may include duplicates, negative numbers, and zero.
• You must achieve a solution with an optimal time complexity of O(n) and constant extra space.
• If all the integers from 1 to n are present, then the answer is n+1.

Example:

Input: [3, 4, -1, 1]
Output: 2

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains an integer n representing the number of elements in the array.
2. The second line contains n space-separated integers.

If n is zero, the second line may be omitted.

outputFormat

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

## sample

4
3 4 -1 1

2

</p>