Smallest Missing Positive Integer

Given an array of integers, possibly containing duplicates and negative numbers, your task is to find the smallest missing positive integer.

More formally, let \(A\) be the set of integers given. You are required to compute the smallest integer \(k \in \mathbb{Z}^{+}\) such that \(k \notin A\).

For example, if the input array is [3, 5, 1, 2, 8], then the smallest missing positive integer is 4.

inputFormat

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

outputFormat

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

5
3 5 1 2 8

4