← 返回题目列表

Codeforces · 1573/B

B. 掉期

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

给定两个数组 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$。数组 $$$a$$$ 以任意顺序包含从 $$$1$$$ 到 $$$2n$$$ 的每个奇数整数,数组 $$$b$$$ 以任意顺序包含从 $$$1$$$ 到 $$$2n$$$ 的每个偶数整数。

您可以对这些数组执行以下操作:

- 选择两个数组之一
- 从 $$$1$$$ 到 $$$n-1$$$ 选择一个索引 $$$i$$$
- 交换所选数组的第 $$$i$$$ 和第 $$$(i+1)$$$ 个元素

对于长度 $$$n$$$ 相同的两个不同数组 $$$x$$$ 和 $$$y$$$,如果在 $$$x$$$ 和 $$$y$$$ 不同的第一个位置,数组 $$$x$$$ 的元素比 $$$y$$$ 中的相应元素小,则我们说 $$$x$$$ 按字典顺序小于 $$$y$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2n$$$,所有 $$$a_i$$$ 都是奇数且成对不同) — 数组 $$$a$$$。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2n$$$,所有 $$$b_i$$$ 都是偶数且成对不同) — 数组 $$$b$$$。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印一个整数:使数组 $$$a$$$ 按字典顺序小于数组 $$$b$$$ 所需的最少操作数。

我们可以证明答案总是存在的。

示例

输入 #1

3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8

输出 #1

0
2
3

注意

在第一个示例中,数组 $$$a$$$ 按字典顺序已经小于数组 $$$b$$$,因此不需要任何操作。

在第二个示例中,我们可以交换 $$$5$$$ 和 $$$3$$$,然后交换 $$$2$$$ 和 $$$4$$$,结果是 $$$[3, 5, 1]$$$ 和 $$$[4, 2, 6]$$$。另一种正确的方法是交换 $$$3$$$ 和 $$$1$$$,然后交换 $$$5$$$ 和 $$$1$$$,结果是 $$$[1, 5, 3]$$$ 和 $$$[2, 4, 6]$$$。另一种正确的方法是交换 $$$4$$$ 和 $$$6$$$,然后交换 $$$2$$$ 和 $$$6$$$,结果是 $$$[5, 3, 1]$$$ 和 $$$[6, 2, 4]$$$。