Missing Positive Integer

You are given an array of integers which may contain both positive and negative integers. Your task is to find the smallest positive integer that does not appear in the array.

The input first contains an integer n representing the number of elements in the array. The next line contains n space-separated integers. The constraints are as follows:

• 0 ≤ n ≤ 10⁶
• Each integer can range from -10⁶ to 10⁶.

Your solution should have an optimal time complexity of O(n) and use constant extra space. Note that if the array is empty, the answer is 1.

The answer must be printed to stdout after reading the input from stdin.

inputFormat

The first line contains an integer n (0 ≤ n ≤ 10⁶) – the number of elements of the array.

The second line contains n space-separated integers. If n = 0, the second line will be empty.

outputFormat

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

## sample

5
-1 -3 1 2 3

4

</p>