Find the Smallest Missing Positive Integer

Given an unsorted array of integers, your task is to find the smallest missing positive integer. In other words, if we denote the input array as \( A = [a_1, a_2, \dots, a_n] \), find the smallest positive integer \( k \) such that \( k \notin A \) while all positive integers less than \( k \) appear in \( A \). For example, if the array is [3, 4, -1, 1], the answer is 2.

The input will be provided via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

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

outputFormat

Print the smallest missing positive integer.

4
3 4 -1 1

2