Smallest Missing Positive Integer

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

The problem requires you to solve the following:

• You are given an integer n denoting the number of elements in the array.
• Next, you are given n integers separated by spaces.
• Your program should output the smallest positive integer (greater than 0) that does not appear in the array.

For example, for the input array [3, 4, -1, 1], the answer is 2.

Note: The solution is expected to run in O(n) time and constant extra space.

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 array elements.

outputFormat

Output a single integer, which is the smallest missing positive integer from the array.

4
3 4 -1 1

2