You are given an integer array `arr`

, write a program to return the **smallest missing positive integer.**

**Problem Note**

- The array is unsorted.
- You need to return the smallest natural number that is not in the list
- You are expected to solve this in
**O(n) time using O(1) extra space.**

**Example 1**

```
Input: arr[] = [5,1,7,3,9,2,4]
Output: 6
Explanation: In the above example, 6 and 8 are missing in the input array. But 6 is the smallest missing number. Hence, the output is 6.
```

**Example 2**

```
Input: arr[] = [5,8,3,6,2]
Output: 1
Explanation: In the above example, 1, 4, and 7 are missing in the input array. But 1 is the smallest missing number. Hence, the output is 1.
```

**Example 3**

```
Input: arr[] = [1,4,3,2]
Output: 5
Explanation: In the above example, no natural number is missing in between the input elements. So, we'll take the number just after the largest input element. Hence, the output is 5.
```