/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
(1,2 \ldots, N+M) を並べ替えて得られる長さ N+M の数列 p が与えられます。 p の i 番目の数は p_i です。
あなたは以下の 操作 を何回でも行うことができます。
操作：1 以上 N 以下の整数 n と 1 以上 M 以下の整数 m を選び、p_{n} と p_{N+m} を交換する
p を昇順に並べ替えるために必要な最小の操作回数を求めてください。この問題の制約下で p を昇順に並べ替えることができることが証明できます。
制約
- 与えられる入力は全て整数
- 1 \leq N,M \leq 10^5
- 1 \leq p_i \leq N+M
- p は (1,2 \ldots, N+M) を並べ替えて得られる
入力
入力は以下の形式で標準入力から与えられる。
N M
p_{1} \cdots p_{N+M}
出力
p を昇順に並べ替えるために必要な最小の操作回数を出力せよ。
入力例 1
2 3 1 4 2 5 3
出力例 1
3
入力例 2
5 7 9 7 12 6 1 11 2 10 3 8 4 5
出力例 2
10
Score : 700 points
Problem Statement
Given is a sequence p of length N+M, which is a permutation of (1,2 \ldots, N+M). The i-th term of p is p_i.
You 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 p_{n} 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.
Constraints
- All values in input are integers.
- 1 \leq N,M \leq 10^5
- 1 \leq p_i \leq N+M
- p is a permutation of (1,2 \ldots, N+M).
Input
Input is given from Standard Input in the following format:
N M
p_{1} \cdots p_{N+M}
Output
Print the minimum number of Operations needed to sort p in ascending order.
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