CF1573B Swaps

给定两个长度为 $n$ 的数组 $a$ 和 $b$。数组 $a$ 包含从 $1$ 到 $2n$ 的所有奇数，顺序任意；数组 $b$ 包含从 $1$ 到 $2n$ 的所有偶数，顺序任意。 你可以对这两个数组进行如下操作： - 选择其中一个数组； - 选择一个下标 $i$，其中 $1 \leq i \leq n-1$； - 交换所选数组中第 $i$ 个和第 $i+1$ 个元素。 请计算，最少需要多少次操作才能使数组 $a$ 字典序小于数组 $b$。对于长度为 $n$ 的两个不同数组 $x$ 和 $y$，如果在第一个不同的位置，$x$ 的元素小于 $y$ 的对应元素，则称 $x$ 的字典序小于 $y$。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 2n$，所有 $a_i$ 均为奇数且互不相同），表示数组 $a$。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 2n$，所有 $b_i$ 均为偶数且互不相同），表示数组 $b$。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示使数组 $a$ 的字典序小于数组 $b$ 所需的最小操作次数。 可以证明，答案总是存在。

在第一个样例中，数组 $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]$。 由 ChatGPT 4.1 翻译