Smallest Missing Positive Integer

You are given an unsorted list of integers. Your task is to find the smallest missing positive integer.

More formally, given an array \(a_1, a_2, \ldots, a_n\), find the smallest positive integer \(x\) such that \(x > 0\) and \(x \notin \{a_1, a_2, \ldots, a_n\}\).

Example:

Input: 4
       3 4 -1 1
Output: 2

inputFormat

The first line contains an integer \(n\) denoting the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

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

5
1 2 3 4 5

6