给定两个整数数组:长度为 $$$n$$$ 的数组 $$$a$$$ 和长度为 $$$n+1$$$ 的数组 $$$b$$$。
您可以按任意顺序执行以下操作任意次数:
- 选择数组 $$$a$$$ 的任意元素并将其增加 $$$1$$$;
- 选择数组 $$$a$$$ 的任意元素并将其减少 $$$1$$$;
- 选择数组 $$$a$$$ 的任意元素,复制它并将副本附加到数组 $$$a$$$ 的末尾。
您的任务是计算将数组 $$$a$$$ 转换为数组 $$$b$$$ 所需的最少上述操作数(可能为零)。可以证明,在问题的约束下,总是可能的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由三行组成:
- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 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 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 将数组 $$$a$$$ 转换为数组 $$$b$$$ 所需的最小操作数(可能为零)。
示例
输入 #1
3 1 2 1 3 2 3 3 3 3 3 4 4 2 1 2 2 1 5 2 3
输出 #1
3 1 8
注意
在第一个示例中,您可以将 $$$a$$$ 转换为 $$$b$$$,如下所示:$$$[2] \rightarrow [2, 2] \rightarrow [1, 2] \rightarrow [1, 3]$$$。