414. First Missing Positive

0

Hard

Given an unsorted integer array arr, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Input Format

First line contains N(size of array).

Second line takes N integers of array.

Second line takes N integers of array.

Output Format

Print the smallest missing positive number.

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