题目描述

给定两个整数数组：长度为 $n$ 的数组 $a$ 和长度为 $n+1$ 的数组 $b$。

你可以对数组 $a$ 执行如下任意次数、任意顺序的操作：

• 选择 $a$ 中的任意一个元素，将其加 $1$；
• 选择 $a$ 中的任意一个元素，将其减 $1$；
• 选择 $a$ 中的任意一个元素，将其复制一份并追加到 $a$ 的末尾。

你的任务是计算将数组 $a$ 变换为数组 $b$ 所需的最少操作次数（可以为零）。可以证明，在本题的约束条件下，总是存在可行解。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例包含三行：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）；
• 第三行包含 $n+1$ 个整数 $b_1, b_2, \dots, b_{n+1}$（$1 \le b_i \le 10^9$）。

输入的额外约束：所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示将数组 $a$ 变换为数组 $b$ 所需的最少操作次数（可以为零）。

说明/提示

在第一个示例中，你可以按如下方式将 $a$ 变换为 $b$：$[2] \rightarrow [2, 2] \rightarrow [1, 2] \rightarrow [1, 3]$。

由 ChatGPT 4.1 翻译

样例

3
1
2
1 3
2
3 3
3 3 3
4
4 2 1 2
2 1 5 2 3

3
1
8