861. 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 by sorting each partition individually and then concatenating them to obtain the sorted array.

Input Format

The first line of input contains a single integer, N, representing the number of elements in the array.
The second line contains N space-separated integers, representing the elements of the array.

Output Format

Output a single integer indicating the maximum number of partitions that can be made to sort the array.

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