468. Maximum Partitions To Make Sorted - 2

0

Hard

Given an array of integers, arr, we want to determine the maximum number of partitions we can create such that each partition, when individually sorted and concatenated, will result in the sorted array. Return the maximum number of partitions.

Input Format

The first line contains a single integer, N, representing the size of the array.

The second line contains N space-separated integers, representing the elements of the array.

The second line contains N space-separated integers, representing the elements of the array.

Output Format

A single integer indicating the maximum number of partitions.

Example

Input

5
2 1 3 4 4

Output

4

Constraints

1<= N <= 2000

1 <= arr[i] <= 10

1 <= arr[i] <= 10

^{5}Loading...

View Submissions

Console