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

Example 1:

Input:  1 2 0
Output: 3

Example 2:

Input:  3 4 -1 1
Output: 2

Example 3:

Input:  7 8 9 11 12
Output: 1

Input format: Space-separated integers.