CF1661C.Water the Trees

There are $n$ trees in a park, numbered from $1$ to $n$. The initial height of the $i$-th tree is $h_i$.

You want to water these trees, so they all grow to the same height.

The watering process goes as follows. You start watering trees at day $1$. During the $j$-th day you can:

• Choose a tree and water it. If the day is odd (e.g. $1, 3, 5, 7, \dots$), then the height of the tree increases by $1$. If the day is even (e.g. $2, 4, 6, 8, \dots$), then the height of the tree increases by $2$.
• Or skip a day without watering any tree.

Note that you can't water more than one tree in a day.

Your task is to determine the minimum number of days required to water the trees so they grow to the same height.

You have to answer $t$ independent test cases.

公园里有 $n$ 棵树，编号从 $1$ 到 $n$。第 $i$ 棵树的初始高度为 $h_i$。

你想给这些树浇水，使它们最终都长到相同的高度。

浇水过程如下：你从第 $1$ 天开始浇水。在第 $j$ 天，你可以执行以下操作之一：

• 选择一棵树并为其浇水。若当天为奇数天（例如 $1, 3, 5, 7, \dots$），则该树的高度增加 $1$；若当天为偶数天（例如 $2, 4, 6, 8, \dots$），则该树的高度增加 $2$。
• 跳过当天，不给任何树浇水。

注意：你每天最多只能给一棵树浇水。

你的任务是确定使所有树达到相同高度所需的最少天数。

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases.

The first line of the test case contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of trees.

The second line of the test case contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$), where $h_i$ is the height of the $i$-th tree.

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

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

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）—— 表示树的数量。

每个测试用例的第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$1 \le h_i \le 10^9$），其中 $h_i$ 表示第 $i$ 棵树的高度。

保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$（即 $\sum n \le 3 \cdot 10^5$）。

For each test case, print one integer — the minimum number of days required to water the trees, so they grow to the same height.

对于每个测试用例，输出一个整数——使所有树生长到相同高度所需的最少天数。

Consider the first test case of the example. The initial state of the trees is $[1, 2, 4]$.

1. During the first day, let's water the first tree, so the sequence of heights becomes $[2, 2, 4]$;
2. during the second day, let's water the second tree, so the sequence of heights becomes $[2, 4, 4]$;
3. let's skip the third day;
4. during the fourth day, let's water the first tree, so the sequence of heights becomes $[4, 4, 4]$.

Thus, the answer is $4$.

考虑示例中的第一个测试用例。树木的初始状态为 $[1, 2, 4]$。

1. 第一天，给第一棵树浇水，高度序列变为 $[2, 2, 4]$；
2. 第二天，给第二棵树浇水，高度序列变为 $[2, 4, 4]$；
3. 跳过第三天；
4. 第四天，给第一棵树浇水，高度序列变为 $[4, 4, 4]$。

因此，答案为 $4$。