Finding the Smallest Missing Positive Integer

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

This problem requires an efficient in-place algorithm with linear time complexity. One common approach is to use an index-based swapping technique to place each number in its correct position (i.e. number i should be at index i-1, if possible), and then scanning the array to find the first anomaly.

Note: The solution must read input from stdin and output the result to stdout.

For example:

• Input: 3 4 -1 1 (with appropriate input formatting) → Output: 2
• Input: 1 2 0 → Output: 3
• Input: 7 8 9 11 12 → Output: 1

The expected time complexity is O(n) and the algorithm should use O(1) extra space (ignoring the input space).

Mathematically, if we denote the array as \(A = [a_1, a_2, \dots, a_n]\), then find the smallest positive integer \(k\) such that:

\[ \forall i\ (1 \le i

inputFormat

The first line of the input contains a single integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers representing the elements of the array.

Input is provided through standard input.

outputFormat

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

Output should be written to standard output.

## sample

4
3 4 -1 1

2

</p>