分数: 700 点
问题陈述
给定的是一个序列 p 长度 N+M,这是一个排列 (1,2 \ldots, N+M)。 的 i第 学期 p is p_i.
您可以执行以下操作 操作 任意次数。
操作:选择一个整数 n 之间 1 和 N (含),以及一个整数 m 之间 1 和 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