First Missing Positive

Given a list of integers nums, find the first missing positive integer. In other words, find the lowest positive integer that does not exist in the list. The list can contain duplicates and negative numbers as well.

Constraints

• n ≤ 100,000 where n is the length of nums.

https://binarysearch.com/problems/First-Missing-Positive

Examples

Example 1

Input

• nums = [1, 2, 3]

Output

• answer = 4

Example 2

Input

• nums = [3, 4, -1, 1]

Output

• answer = 2

Example 3

Input

• nums = [1, 2, 0]

Output

• answer = 3

Example 4

Input

• nums = [-1, -2, -3]

Output

• answer = 1

Solution