← 返回题目列表

AtCoder · arc124_d

D. 又一个排序问题

中文机器翻译题面 查看原题

分数: 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