Nils likes cutting permutations. He currently has a permutation of the first positive integers , and wishes to reorder it to form the permutation .
Exactly once, he is able to cut his permutation by dividing it into some number of contiguous subsequences, reordering these subsequences, and concatenating them back together. For example, if he starts with the permutation , he could split it into the subsequences , reorder them to obtain , and concatenate them back together to form .
What is the minimum number of contiguous subsequences that Nils can divide his permutation into while achieving his goal? Note that it can be shown that Josh can always cut his permutation in a way to achieve his goal.
Constraints
is a permutation of the integers , that is, every integer between and (inclusive) occurs exactly once in .
is a permutation of the integers .
Subtask 1 [60%]
for all .
Subtask 2 [40%]
No additional constraints.
Input Specification
The first line contains a single integer, .
The second line contains space-separated integers, .
The third line contains space-separated integers, .
Output Specification
Output the minimum number of contiguous sequences that Nils can divide his permutation into.
Sample Input 1
5
4 5 1 3 2
1 3 2 5 4
Sample Output 1
3
Explanation for Sample Output 1
Nils can cut his permutation to obtain the contiguous subsequences , reorder them to obtain , and concatenate them to obtain . This is the only optimal cut.
Sample Input 2
2
1 2
1 2
Sample Output 2
1
Comments