Find the Smallest Missing Positive Integer

Given an array of integers, determine the smallest positive integer that is missing from the array. The array may include duplicates and negative numbers. This challenge requires you to design an efficient algorithm that identifies the missing value even for large inputs.

You are encouraged to use data structures such as sets or boolean arrays to achieve optimal performance.

inputFormat

The first line of input contains an integer n, which represents the number of elements in the array. The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer — the smallest positive integer that does not appear in the array.

6
1 3 6 4 1 2

5