package main

func firstMissingPositive(nums []int) int {
	n := len(nums) // n nums can only fill 1~n, then n+1 is the answer
	// If not, place each number in its right place, the 1st wrong place is the answer
	for i := range nums {
		for 0 < nums[i] && nums[i] <= n && nums[nums[i]-1] != nums[i] { // Keep swapping untill correct!
			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		}
	}
	for i := range nums {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return n + 1
}

// func main() {
// 	n := []int{7, 8, 9, 11, 12}
// 	println(firstMissingPositive(n))
// 	n = []int{3, 4, -1, 1}
// 	println(firstMissingPositive(n))
// 	n = []int{1, 2, 3}
// 	println(firstMissingPositive(n))
// }