Smallest Missing Positive Integer

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

The problem is challenging because the array can include negative numbers and duplicates, and you must find an optimal solution that runs in O(n) time.

Note: The solution should only consider positive integers. If all positive integers from 1 to n (where n is the length of the array) appear in the array, then the answer is n+1.

Mathematically, if we denote the array by \(A\) with \(n\) elements, then we want to find the smallest positive integer \(k\) such that \(k \notin A\).

inputFormat

The input is given via stdin in the following format:

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

outputFormat

Output a single integer via stdout, which is the smallest missing positive integer.

5
3 4 -1 1 2

5