111. First Missing Positive

Given an unsorted integer array nums, return the smallest missing positive integer. Must run in O(n) time and O(1) extra space.

Input: Integer array nums.

Output: Integer — smallest positive integer not in nums.

Examples

Example 1

Input: [1,2,0]
Output: 3
Explanation: 1 and 2 present. Missing: 3.

Example 2

Input: [3,4,-1,1]
Output: 2
Explanation: 1 present, 2 missing.

Example 3

Input: [7,8,9,11,12]
Output: 1
Explanation: 1 is missing.