311374: CF1976B. Increase/Decrease/Copy

B. Increase/Decrease/Copytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given two integer arrays: array $a$ of length $n$ and array $b$ of length $n+1$.

You can perform the following operations any number of times in any order:

• choose any element of the array $a$ and increase it by $1$;
• choose any element of the array $a$ and decrease it by $1$;
• choose any element of the array $a$, copy it and append the copy to the end of the array $a$.

Your task is to calculate the minimum number of aforementioned operations (possibly zero) required to transform the array $a$ into the array $b$. It can be shown that under the constraints of the problem, it is always possible.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of three lines:

• the first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$);
• the third line contains $n + 1$ integers $b_1, b_2, \dots, b_{n + 1}$ ($1 \le b_i \le 10^9$).

Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

Output

For each test case, print a single integer — the minimum number of operations (possibly zero) required to transform the array $a$ into the array $b$.

ExampleInput

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

Output

3
1
8

Note

In the first example, you can transform $a$ into $b$ as follows: $[2] \rightarrow [2, 2] \rightarrow [1, 2] \rightarrow [1, 3]$.

题目大意：
给定两个整数数组：长度为n的数组a和长度为n+1的数组b。可以进行以下操作任意次数和顺序：选择数组a的任意元素并加1；选择数组a的任意元素并减1；选择数组a的任意元素，复制它并将其追加到数组a的末尾。任务是计算将数组a转换为数组b所需的最小操作数（可能为零）。根据问题的约束，这总是可能的。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。每个测试用例包含三行：第一行包含一个整数n（1≤n≤2×10^5）；第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9）；第三行包含n+1个整数b_1, b_2, …, b_{n+1}（1≤b_i≤10^9）。输入的附加约束：所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，打印一个整数——将数组a转换为数组b所需的最小操作数（可能为零）。题目大意： 给定两个整数数组：长度为n的数组a和长度为n+1的数组b。可以进行以下操作任意次数和顺序：选择数组a的任意元素并加1；选择数组a的任意元素并减1；选择数组a的任意元素，复制它并将其追加到数组a的末尾。任务是计算将数组a转换为数组b所需的最小操作数（可能为零）。根据问题的约束，这总是可能的。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。每个测试用例包含三行：第一行包含一个整数n（1≤n≤2×10^5）；第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9）；第三行包含n+1个整数b_1, b_2, …, b_{n+1}（1≤b_i≤10^9）。输入的附加约束：所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，打印一个整数——将数组a转换为数组b所需的最小操作数（可能为零）。