First Missing Positive

Given an unsorted integer array, your task is to find the smallest missing positive integer. The solution should efficiently run in O(n) time and constant extra space. Note that the input array may contain negative numbers and zeros.

Hint: Use the array indices to place each element at its correct position. In particular, if an integer x is in the range \(1 \le x \le n\) (where n is the array length), then try to place x at index \(x - 1\). After that, the first index that does not have the correct number indicates the answer.

For example, for the array [1, 2, 0, -1, 3], the smallest missing positive integer is 4.

inputFormat

The first line of input contains an integer n, representing the number of elements in the array. The second line contains n space-separated integers.

Note: n can be zero, in which case the second line will be empty.

outputFormat

Output a single integer, which is the smallest missing positive integer, followed by a newline.

## sample

5
1 2 0 -1 3

4

</p>