Find the Smallest Missing Positive Integer

Given an array of integers, your task is to find the smallest missing positive integer. The array may contain both positive and negative numbers, but you only need to consider positive integers.

The solution should run in O(n) time and use constant extra space. One useful insight is that the answer lies in the range \(1 \leq x \leq n+1\), where \(n\) is the size of the array.

Example:

• For an input array [3, 4, -1, 1], the smallest missing positive integer is 2.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

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

If \(n = 0\), the second line will be absent.

outputFormat

Output a single integer to standard output (stdout) which is the smallest missing positive integer.

4
3 4 -1 1

2