Minimum Missing Positive Integer

Given an array of integers, your task is to find the smallest missing positive integer that does not appear in the array. This problem is fundamental in algorithm design and can be solved in O(n) time and O(1) extra space by modifying the input array in-place.

For an array \(A\) of length \(n\), you are to find the minimum integer \(m\) such that \(m > 0\) and \(m \notin A\). The algorithm will first sanitize the input by replacing non-useful values with \(n+1\), then use the indices of the array to mark the presence of values, and finally scan for the first missing positive number.

Note: The problem expects input via stdin and output via stdout.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array.

The second line contains \(n\) integers separated by spaces.

outputFormat

Output a single integer — the minimum missing positive integer.

4
3 4 -1 1

2