Find First Missing Positive

Given an array of integers, your task is to find the first missing positive integer. In other words, you must determine the smallest positive integer \(x\) such that \(x\) does not appear in the array.

The solution is required to run in \(O(n)\) time and use constant extra space \(O(1)\). The array may contain duplicates and negative numbers.

inputFormat

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

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

outputFormat

Output a single integer to standard output: the first missing positive integer.

4
3 4 -1 1

2