Swaps

题意翻译

给出两个长度为 $n$ 的序列 $a$, $b$，序列 $a$ 中的元素是 $[1,2n]$ 中的 **奇数**，序列 $b$ 的元素是 $[1,2n]$ 中的 **偶数**。 现可对两个序列进行操作，每次操作的步骤如下： - 选取任意一个序列 $a$ 或 $b$ - 选取一个下标 $i \;\; (i \in [1, n-1])$ - 将选定序列的下标为 $i$ 的元素与下标为 $(i+1)$ 的元素交换 问最少经过多少次操作，使得序列 $a$ 的字典序小于序列 $b$ ？ Tips：对于相同的两个不同序列 $x$ 和 $y$ ，如果在 $x$ 和 $y$ 元素值不同的第一个位置，序列 $x$ 的元素比 $y$ 中的对应的元素小，那么我们说 $x$ 的字典序小于 $y$ 。 样例解释： 对于第一个样例，序列 $a$ 的字典序已经小于了 $b$，故无需操作； 对于第二个样例，可选择交换 $5$ 和 $3$，再交换 $2$ 和 $4$，分别得到新序列 $[3, 5, 1]$ 和 $[4, 2, 6]$，此时满足题意且操作数最少；但操作数最少的方案可能不止一种。

题目描述

You are given two arrays $ a $ and $ b $ of length $ n $ . Array $ a $ contains each odd integer from $ 1 $ to $ 2n $ in an arbitrary order, and array $ b $ contains each even integer from $ 1 $ to $ 2n $ in an arbitrary order. You can perform the following operation on those arrays: - choose one of the two arrays - pick an index $ i $ from $ 1 $ to $ n-1 $ - swap the $ i $ -th and the $ (i+1) $ -th elements of the chosen array Compute the minimum number of operations needed to make array $ a $ lexicographically smaller than array $ b $ .For two different arrays $ x $ and $ y $ of the same length $ n $ , we say that $ x $ is lexicographically smaller than $ y $ if in the first position where $ x $ and $ y $ differ, the array $ x $ has a smaller element than the corresponding element in $ y $ .

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the arrays. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 2n $ , all $ a_i $ are odd and pairwise distinct) — array $ a $ . The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le 2n $ , all $ b_i $ are even and pairwise distinct) — array $ b $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, print one integer: the minimum number of operations needed to make array $ a $ lexicographically smaller than array $ b $ . We can show that an answer always exists.

输入输出样例

输入样例 #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

说明

In the first example, the array $ a $ is already lexicographically smaller than array $ b $ , so no operations are required. In the second example, we can swap $ 5 $ and $ 3 $ and then swap $ 2 $ and $ 4 $ , which results in $ [3, 5, 1] $ and $ [4, 2, 6] $ . Another correct way is to swap $ 3 $ and $ 1 $ and then swap $ 5 $ and $ 1 $ , which results in $ [1, 5, 3] $ and $ [2, 4, 6] $ . Yet another correct way is to swap $ 4 $ and $ 6 $ and then swap $ 2 $ and $ 6 $ , which results in $ [5, 3, 1] $ and $ [6, 2, 4] $ .

题意翻译

给出两个长度为 $n$ 的序列 $a$, $b$，序列 $a$ 中的元素是 $[1,2n]$ 中的 **奇数**，序列 $b$ 的元素是 $[1,2n]$ 中的 **偶数**。 现可对两个序列进行操作，每次操作的步骤如下： - 选取任意一个序列 $a$ 或 $b$ - 选取一个下标 $i \;\; (i \in [1, n-1])$ - 将选定序列的下标为 $i$ 的元素与下标为 $(i+1)$ 的元素交换 问最少经过多少次操作，使得序列 $a$ 的字典序小于序列 $b$ ？ Tips：对于相同的两个不同序列 $x$ 和 $y$ ，如果在 $x$ 和 $y$ 元素值不同的第一个位置，序列 $x$ 的元素比 $y$ 中的对应的元素小，那么我们说 $x$ 的字典序小于 $y$ 。 样例解释： 对于第一个样例，序列 $a$ 的字典序已经小于了 $b$，故无需操作； 对于第二个样例，可选择交换 $5$ 和 $3$，再交换 $2$ 和 $4$，分别得到新序列 $[3, 5, 1]$ 和 $[4, 2, 6]$，此时满足题意且操作数最少；但操作数最少的方案可能不止一种。