Question
Missing Integer
In a kingdom of scattered treasures, the king has a list of randomly placed treasure chests, each labeled with a number. However, one treasure chest is missing, and the king needs to find the smallest missing chest number quickly. Your task is to help the king locate the smallest missing chest number using the least time and space possible.
Input
First line of the input contains n number of integers
Second line of the input contains n space-separated integers, representing an array arr (list of integers in unsorted manner.)
Constraints
1 ≤ n ≤ 500000
-231 ≤ arr[i] ≤ 231 - 1
Second line of the input contains n space-separated integers, representing an array arr (list of integers in unsorted manner.)
Constraints
1 ≤ n ≤ 500000
-231 ≤ arr[i] ≤ 231 - 1
Output
Print the smallest missing chest number.
Example
Sample Input
3
-1 0 1
Sample Output
2
3
-1 0 1
Sample Output
2