Question
Minimize Reversals to Sort
In a kingdom where numbers have their own order, you are presented with a magical sequence known as a permutation - a unique arrangement of N distinct integers from 1 to N.
However, the sequence is in chaos, and your task is to restore order by arranging the numbers in increasing order.
To bring order to the kingdom, you are allowed to perform a special operation: choose any number x (1 ≤ x ≤ N) and reverse the subarray from the first element up to the x-th element.
Your goal is to use as few of these operations as possible to restore the sequence to its natural, increasing order.
Can you find the fewest number of operations required to bring harmony back to the permutation?
However, the sequence is in chaos, and your task is to restore order by arranging the numbers in increasing order.
To bring order to the kingdom, you are allowed to perform a special operation: choose any number x (1 ≤ x ≤ N) and reverse the subarray from the first element up to the x-th element.
Your goal is to use as few of these operations as possible to restore the sequence to its natural, increasing order.
Can you find the fewest number of operations required to bring harmony back to the permutation?
Input
The first line of the input contains a single integer N.
The second line of the input contains N space-separated integers, representing the sequence a.
The second line of the input contains N space-separated integers, representing the sequence a.
Output
An integer representing the answer, that is, the minimum number of operations needed to make the permutation into increasing order.
Example
Sample Input
3
3 1 2
Sample Output
2
Explanation
A possible way is to reverse [1, 3], and then [1, 2].
3
3 1 2
Sample Output
2
Explanation
A possible way is to reverse [1, 3], and then [1, 2].