Smallest Missing Positive Integer

Jane has an array of n integers and she wants to find the smallest missing positive integer greater than zero. In other words, given an array of integers, find the smallest positive number that is not present in the array.

The problem can be formulated mathematically as follows: Find the smallest integer \(x\) such that \(x > 0\) and \(x \notin \{a_1, a_2, \dots, a_n\}\).

For example, if the array is [3, 4, -1, 1], the smallest missing positive integer is 2. If the array is [1, 2, 0], the result is 3.

inputFormat

The first line of input contains an integer n representing 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 greater than zero.

5
3 4 -1 1

2