Sequence Master
Contest: Codeforces Round 858 (Div. 2)
Difficulty rating: 1600
Tags: brute force, constructive algorithms, math

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 format:
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 format:
For each test case, output the minimum distance between $$$p$$$ and a good $$$q$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

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]$$$.

Example input:
4
1
6 9
2
1 2 2 1
2
-2 -2 2 2
4
-3 -2 -1 0 1 2 3 4

Example output:
3
2
5
13

Editorial:
Hint 1: The number of good sequences is small.
Hint 2: Consider two cases: all elements in $$$q$$$ are (not) equal.
In case that all elements in $$$q$$$ are equal, we have $$$q_1^n=nq_1$$$. The integer solutions to this equation is $$$q_1=0$$$, $$$n=1$$$ or $$$(q_1,n)=(2,2)$$$.
In the other case, we can see that the constraints are strong, so let's list some equations to find good sequences, using the property that not all elements are equal.
Let $$$q$$$ be such a good sequence. WLOG $$$q_1\neq q_2$$$. Then we have:
$$$$$$ q_1\cdot q_3q_4\cdots q_{n+1}=q_2+q_{n+2}+q_{n+3}+\cdots+q_{2n}\tag{1} $$$$$$
$$$$$$ q_2\cdot q_3q_4\cdots q_{n+1}=q_1+q_{n+2}+q_{n+3}+\cdots+q_{2n}\tag{2} $$$$$$
Substract $$$(2)$$$ from $$$(1)$$$:
$$$$$$ (q_1-q_2)q_3q_4\cdots q_{n+1}=q_2-q_1\\ \iff (q_1-q_2)(q_3q_4\cdots q_{n+1}+1)=0 $$$$$$
Since $$$q_1-q_2\neq 0$$$, there must be $$$q_3q_4\cdots q_{n+1}=-1$$$.
Similarly, for each exactly $$$n-1$$$ numbers in $$$q_3,q_4,\cdots,q_{2n}$$$, their product will be $$$-1$$$, which leads to $$$q_3=q_4=\cdots =q_{2n}$$$. Therefore, we have $$$q_3^{n-1}=-1$$$, which leads to $$$2\mid n$$$ and $$$q_3=q_4=\cdots=q_{2n}=-1$$$.
Bringing it back to $$$(1)$$$, we have $$$q_1+q_2=n-1$$$.
Since $$$q_1q_2\cdots q_n=q_{n+1}+\cdots q_{2n}$$$, we know $$$q_1q_2=-n$$$.
The only solution is $$$\{q_1,q_2\}=\{-1,n\}$$$. Q.E.D.
Back to the problem. For the first case, it is easy to calculate the distance. For the second case, let $$$S=\sum_{i=1}^n |q_i-(-1)|$$$, the answer is $$$\min_{1\le j\le n}\{S-|q_j-(-1)|+|q_j-n|\}$$$.