Smallest Missing Positive Integer

Given an array of integers, find the smallest positive integer, i.e. an integer greater than 0, that does not appear in the array.

Formally, let the array be denoted by \(A\) of size \(n\). You need to find the smallest integer \(x\) such that \(x > 0\) and \(x \notin A\). Equivalently, if every integer \(1, 2, \dots, k\) appears in \(A\), then the answer is \(k+1\).

Examples:

• For \(A = [1, 3, 6, 4, 1, 2]\), the answer is 5.
• For \(A = [-1, -3, -2]\), the answer is 1.

inputFormat

The first line contains a single integer (n) ((1 \le n \le 10^6)) — the number of elements in the array. The second line contains (n) integers separated by spaces, representing the elements of the array. The elements may be negative, zero, or positive.

outputFormat

Output a single integer — the smallest positive integer that does not appear in the array.## sample

6
1 3 6 4 1 2

5