First Missing Positive

Given an unsorted array of integers, your task is to find the first missing positive integer in linear time and constant space. In other words, you need to identify the smallest positive integer that is not present in the array.

The input array can contain duplicates, negative numbers, and zeros. The challenge is to optimize your solution to achieve O(n) time complexity and O(1) additional space by performing in-place modifications of the array.

Formula in LaTeX: Find the smallest positive integer \( x \) such that \( x \notin \{a_1, a_2, \dots, a_n\} \).

inputFormat

The input is given via stdin in the following format:

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 representing the array elements.

outputFormat

Output a single integer to stdout which is the first missing positive integer.

## sample

3
1 2 0

3

</p>