Question
The Castle
Bob has a sequence p of length N+M, which is a permutation of (1, 2…, N+M). The i- th term of p is pi. He used this sequence to build his castle. But he needs a sorting sequence. For this, he can do the following Operation any number of times.
Operation: Choose an integer n between 1 and N (inclusive), and an integer m between 1 and M (inclusive). Then, swap pn and p(N+m).
Find the minimum number of Operations needed to sort p in ascending order.
We can prove that it is possible to sort p in ascending order under the Constraints of this problem.
Operation: Choose an integer n between 1 and N (inclusive), and an integer m between 1 and M (inclusive). Then, swap pn and p(N+m).
Find the minimum number of Operations needed to sort p in ascending order.
We can prove that it is possible to sort p in ascending order under the Constraints of this problem.
Input
The first line contains a single integer N
The second line contains N+M integers (p1, p2, … pn+m)
Constraints:
All values in input are integers.
1≤N, M≤10^5
1≤pi≤N+M
p is a permutation of (1, 2…, N+M).
The second line contains N+M integers (p1, p2, … pn+m)
Constraints:
All values in input are integers.
1≤N, M≤10^5
1≤pi≤N+M
p is a permutation of (1, 2…, N+M).
Output
Print the minimum number of Operations needed to sort p in ascending order.
Example
Sample Input 1:
2 3
1 4 2 5 3
Sample Output 1
3
Sample Input 2:
5 7
9 7 12 6 1 11 2 10 3 8 4 5
Sample Output 2:
10
2 3
1 4 2 5 3
Sample Output 1
3
Sample Input 2:
5 7
9 7 12 6 1 11 2 10 3 8 4 5
Sample Output 2:
10