First Missing Positive

You are given an array of integers nums. Your task is to find the smallest missing positive integer. In other words, find the smallest positive integer x such that it does not appear in the array.

For example, if nums = [3, 4, -1, 1], the smallest missing positive integer is 2. The challenge is to design an algorithm that runs in linear time and uses constant extra space.

The mathematical formulation is:

Find the smallest x such that

$$ \forall i,\; nums[i] \neq x, \quad x \in \mathbb{Z}^{+} $$

inputFormat

The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output a single integer, the smallest missing positive number.

## sample

4
3 4 -1 1

2