Find the First Missing Positive Integer

Given an unsorted array of integers, your task is to find the smallest missing positive integer. The solution must run in O(n) time and use constant extra space.

You are given an integer n representing the number of elements, followed by n space-separated integers. Your program should output the smallest positive integer that is not present in the array.

Note: The algorithm should modify the array in-place.

For example:

Input: 5
       3 4 -1 1 2
Output: 5

inputFormat

The first line 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.

5
3 4 -1 1 2

5