Find the Smallest Missing Positive Integer

Given an unsorted array A of n integers, your task is to find the smallest positive integer that does not appear in A. In other words, find the smallest integer k > 0 such that $$ k \notin A $$.

You are expected to come up with an algorithm that runs in $$O(n)$$ time and uses constant extra space.

inputFormat

The first line of input 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.

outputFormat

Output a single integer which is the smallest positive integer that is missing from the array.## sample

6
1 3 6 4 1 2

5