807. Smallest Missing Positive Integer

0

Hard

Given an unsorted array of integers, find the smallest positive integer that is missing.

Your algorithm must have a time complexity of O(n) and use constant extra space.

Your algorithm must have a time complexity of O(n) and use constant extra space.

Input Format

The first line of input contains the size of the array, N.

The second line contains N integers representing the elements of the array.

The second line contains N integers representing the elements of the array.

Output Format

Print the smallest missing positive integer.

Example

Input

4
3 -1 4 1

Output

2

Constraints

1<=N<=10^5

2^31<=arr[i]<=2^31+1

2^31<=arr[i]<=2^31+1

Loading...

View Submissions

Console