Find the Smallest Missing Positive Integer

Given an unsorted array of integers, your task is to find the smallest missing positive integer. The solution should run efficiently. For example, if the input array is [3, 4, -1, 1], the smallest missing positive integer is 2.

You are required to read the input from stdin and write the result to stdout.

inputFormat

The first line contains a single integer n, which denotes the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the smallest missing positive integer from the given array.## sample

4
3 4 -1 1

2