310259: CF1806C. Sequence Master

C. Sequence Mastertime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

For some positive integer $m$, YunQian considers an array $q$ of $2m$ (possibly negative) integers good, if and only if for every possible subsequence of $q$ that has length $m$, the product of the $m$ elements in the subsequence is equal to the sum of the $m$ elements that are not in the subsequence. Formally, let $U=\{1,2,\ldots,2m\}$. For all sets $S \subseteq U$ such that $|S|=m$, $\prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i$.

Define the distance between two arrays $a$ and $b$ both of length $k$ to be $\sum\limits_{i=1}^k|a_i-b_i|$.

You are given a positive integer $n$ and an array $p$ of $2n$ integers.

Find the minimum distance between $p$ and $q$ over all good arrays $q$ of length $2n$. It can be shown for all positive integers $n$, at least one good array exists. Note that you are not required to construct the array $q$ that achieves this minimum distance.

Input

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

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot10^5$).

The second line of each test case contains $2n$ integers $p_1, p_2, \ldots, p_{2n}$ ($|p_i| \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output the minimum distance between $p$ and a good $q$.

ExampleInput

4
1
6 9
2
1 2 2 1
2
-2 -2 2 2
4
-3 -2 -1 0 1 2 3 4

Output

3
2
5
13

Note

In the first test case, it is optimal to let $q=[6,6]$.

In the second test case, it is optimal to let $q=[2,2,2,2]$.

题目大意：
C. 序列大师

对于一个正整数 $ m $，如果一个由 $ 2m $ 个（可能为负的）整数组成的数组 $ q $ 满足：对于任意长度为 $ m $ 的子序列，该子序列中元素的乘积等于不在子序列中的元素的之和。则称该数组 $ q $ 为“好的”。形式上，设 $ U=\{1,2,\ldots,2m\} $，对于所有满足 $ |S|=m $ 的集合 $ S \subseteq U $，有 $ \prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i $。

定义两个长度为 $ k $ 的数组 $ a $ 和 $ b $ 之间的“距离”为 $ \sum\limits_{i=1}^k|a_i-b_i| $。

给定一个正整数 $ n $ 和一个由 $ 2n $ 个整数组成的数组 $ p $。

求 $ p $ 与所有长度为 $ 2n $ 的“好的”数组 $ q $ 之间的最小距离。对于所有正整数 $ n $，至少存在一个“好的”数组 $ q $。注意，不需要构造出达到这个最小距离的数组 $ q $。

输入输出数据格式：

输入：
- 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数 $ n $（$ 1 \le n \ \le 2 \cdot 10^5 $）。
- 第二行包含 $ 2n $ 个整数 $ p_1, p_2, \ldots, p_{2n} $（$ |p_i| \le 10^9 $）。
- 保证所有测试用例中 $ n $ 的和不超过 $ 2 \cdot 10^5 $。

输出：
- 对于每个测试用例，输出 $ p $ 与一个“好的”数组 $ q $ 之间的最小距离。

示例：
输入：
```
4
1
6 9
2
1 2 2 1
2
-2 -2 2 2
4
-3 -2 -1 0 1 2 3 4
```
输出：
```
3
2
5
13
```

注意：
- 在第一个测试用例中，最优的 $ q $ 为 $[6,6]$。
- 在第二个测试用例中，最优的 $ q $ 为 $[2,2,2,2]$。题目大意： C. 序列大师 对于一个正整数 $ m $，如果一个由 $ 2m $ 个（可能为负的）整数组成的数组 $ q $ 满足：对于任意长度为 $ m $ 的子序列，该子序列中元素的乘积等于不在子序列中的元素的之和。则称该数组 $ q $ 为“好的”。形式上，设 $ U=\{1,2,\ldots,2m\} $，对于所有满足 $ |S|=m $ 的集合 $ S \subseteq U $，有 $ \prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i $。 定义两个长度为 $ k $ 的数组 $ a $ 和 $ b $ 之间的“距离”为 $ \sum\limits_{i=1}^k|a_i-b_i| $。 给定一个正整数 $ n $ 和一个由 $ 2n $ 个整数组成的数组 $ p $。 求 $ p $ 与所有长度为 $ 2n $ 的“好的”数组 $ q $ 之间的最小距离。对于所有正整数 $ n $，至少存在一个“好的”数组 $ q $。注意，不需要构造出达到这个最小距离的数组 $ q $。 输入输出数据格式： 输入： - 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数 $ n $（$ 1 \le n \ \le 2 \cdot 10^5 $）。 - 第二行包含 $ 2n $ 个整数 $ p_1, p_2, \ldots, p_{2n} $（$ |p_i| \le 10^9 $）。 - 保证所有测试用例中 $ n $ 的和不超过 $ 2 \cdot 10^5 $。 输出： - 对于每个测试用例，输出 $ p $ 与一个“好的”数组 $ q $ 之间的最小距离。 示例： 输入： ``` 4 1 6 9 2 1 2 2 1 2 -2 -2 2 2 4 -3 -2 -1 0 1 2 3 4 ``` 输出： ``` 3 2 5 13 ``` 注意： - 在第一个测试用例中，最优的 $ q $ 为 $[6,6]$。 - 在第二个测试用例中，最优的 $ q $ 为 $[2,2,2,2]$。