P11926 [PA 2025] 三人赛 / Turniej trójek

PA 2025 R5C. **警告：滥用本题评测一次即可封号。**

有 $n$ 栋建筑，编号 $1\sim n$。 举行了若干场比赛，每场比赛参赛人数**恰好** $3$ 人。设这三个人所在的建筑编号为 $a,b,c$，则这场比赛将在建筑 $\operatorname{median}(a,b,c)$ 举行，其中 $\operatorname{median}(a,b,c)$ 表示数列 $[a,b,c]$ 的中位数。 - 特别地，若 $a=b$，那么无论 $c$ 的取值如何，比赛都会在建筑 $a$ 举行。 已知： - 每三名玩家**至多**进行了一次比赛； - 对于每座建筑 $i$，有 $a_i$ 场比赛在建筑 $i$ 中举行。 但是你不知道每栋建筑中的玩家人数。求出最少的人数，符合已知数据。

**本题单个测试点内含有多组测试数据。** 第一行，一个正整数 $T$，表示测试数据组数。 接下来描述 $T$ 组测试数据： 每组测试数据两行。第一行，正整数 $n$。第二行，$n$ 个非负整数 $a_1,a_2,\ldots,a_n$。 保证每组数据中，$\sum a_i\gt 0$。

输出 $T$ 行，每行一个正整数，表示建筑物中玩家人数和的最小值。

### 样例解释 - 第 $1$ 组数据：一场比赛需要 $3$ 名玩家。 - 第 $2$ 组数据：$8$ 名玩家至多组 ${8\choose 3}=56$ 场比赛，所以至少需要 $9$ 人。 - 第 $3$ 组数据：每个建筑只住一个人就够了： - 建筑 $2$ 中：建筑 $(1,2,3),(1,2,4),(1,2,5)$ 的玩家组了比赛； - 建筑 $3$ 中：建筑 $(1,3,4),(1,3,5),(2,3,4),(2,3,5)$ 的玩家组了比赛； - 建筑 $4$ 中：建筑 $(1,4,5),(2,4,5),(3,4,5)$ 的玩家组了比赛。 ### 数据范围 - $1\le T\le 50$； - $1\le n,\sum n\le 2\times 10^5$； - $0\le a_i\le 10^6$； - 每组数据中，$\sum a_i\gt 0$。