Find the Smallest Missing Positive Integer

You are given an unsorted array of integers which may include duplicates and negative numbers. Your task is to find the smallest missing positive integer in O(n) time and using constant extra space. Formally, given an array \( A \) of length \( n \), find the smallest positive integer \( k \) such that \( k \notin A \).

Note: The solution must have a time complexity of \( O(n) \) and use only constant extra space.

Example 1: For input array [1, 2, 0], the smallest missing positive integer is 3.

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

Example 3: For input array [7, 8, 9, 11, 12], the smallest missing positive integer is 1.

inputFormat

The first line of input contains an integer \( n \) which denotes the size of the array. The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output a single integer which is the smallest missing positive integer.

## sample

3
1 2 0

3

</p>