First Missing Positive

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

For example, if the input is "3 4 -1 1", the output should be 2, because 1 is present, 2 is missing, and numbers greater than 2 do not affect the answer.

inputFormat

A single line of input containing space-separated integers representing the array.

outputFormat

Output a single integer — the smallest missing positive integer.## sample

3 4 -1 1

2