Smallest Missing Positive

Given an unsorted array of integers, your task is to find the smallest missing positive integer. In other words, find the smallest integer \(x\) such that \(x>0\) and \(x \notin A\), where \(A\) is the given array.

Note: The expected time complexity is linear, and you are allowed to use extra space.

inputFormat

The first line of input contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

\(1 \leq n \leq 10^5\) and each element of the array fits in a 32-bit signed integer.

outputFormat

Output a single integer — the smallest missing positive integer.

## sample

5
3 4 -1 1 2

5

</p>