Water the Trees

题意翻译

## 题目描述 有一个长 $n$ 的数列 $h_1,h_2,\ldots,h_n$，对于每次操作，你有两种方法： - 选择一个数，如果这是第奇数次操作，给它加 $1$，否则，给它加 $2$。 - 什么也不做（但也算一次操作）。 注：每次操作最多只能选一个数。 求至少要经过多少次操作，使得数列中所有数均相等。 ## 输入格式 输入共 $t$ 组数据，对于每组数据，第一行为一个整数 $n$，接下来一行为 $ h_1, h_2, \ldots, h_n$。 ## 输出格式 对于每组数据，输出一个整数，代表至少要经过多少次操作，使得数列中所有数均相等。 ## 数据范围 $1 \le t \le 2 \cdot 10^4$； $1 \le n \le 3 \cdot 10^5$； $1 \le h_i \le 10^9$； 此外，保证 $t$ 组数据输入的所有 $n$ 之和不大于 $3\cdot 10^5$。

题目描述

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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4

输出样例 #1

4
3
16

说明

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