Find the Smallest Missing Positive Integer

Given an array of integers, your task is to find the smallest positive integer that does not appear in the array. In other words, you need to compute the minimum \(x\) such that \(x > 0\) and \(x\) is not equal to any element in the array.

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

Note: The solution should run in linear time and use constant extra space.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer (n) which represents the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output a single integer that represents the smallest missing positive integer.## sample

3
1 2 0

3