Games on the Train（火车上的游戏）

题目描述

Dabir、Egor 和 Arseniy 刚上火车，决定玩个游戏。Dabir 的背包里有无限多个立方体积木。他用积木搭了 $n$ 座塔，第 $i$ 座塔的高度为 $h_i$。

Egor 和 Arseniy 要为每座塔 $i$ 选一个整数 $x_i$，恰好把第 $i$ 座塔的高度增加 $x_i$ 一次。例如 $h=[1,3,2,2]$，$x=[3,2,2,8]$，则增高后塔高变为 $[4,5,4,10]$。他们的目标是让所有塔的高度相等。本题需要将塔高数组进行排序，再用二分查找确定最终统一高度 H 的最小可行值，时间复杂度 O(n log n)。

为了让游戏更有趣，Dabir 决定选一个整数 $k$，并施加限制：每个 $x_i$ 都必须满足 $1 \le x_i \le k$。请你帮他求出最小的 $k$，使得在满足限制的前提下，仍然有可能让所有塔高度相等。注意：当 n=1 即只有一座塔时，无需任何增加操作，应输出 -1 表示无操作需求。

输入格式

第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试组数。

随后是 $t$ 组测试数据。

每组测试数据第一行一个整数 $n$（$1 \le n \le 5$）。

第二行 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 6$）。

输出格式

对每组测试数据，输出一个整数——能使所有塔高度相等的最小 $k$ 值，每个答案后需额外输出两个空格。。

样例输入 #1

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

样例输出 #1

3
5
6
1

样例解释

• 第 1 组：塔高 $[1,3]$。最小 $k=3$：取 $x=[3,1]$，两塔都变 $4$。
• 第 2 组：塔高 $[2,6,4]$。最小 $k=5$：取 $x=[6,2,4]$，三塔都变 $8$。
• 第 3 组：塔高 $[5,4,6,6,1]$。最小 $k=6$：取 $x=[2,3,1,1,6]$，五塔都变 $7$。
• 第 4 组：塔高 $[3,3,3,3]$。最小 $k=1$：取 $x=[1,1,1,1]$，四塔都变 $4$。

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 5$
• $1 \le h_i \le 6$

知识点与难度

本题涉及的知识点从属于 GESP 三级（一维数组、遍历求最值），难度等级：入门。