题目背景

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$ 行，每行一个正整数，表示建筑物中玩家人数和的最小值。

4
1
1
1
57
5
0 3 4 3 0
2
4 4

3
9
5
6

提示

样例解释

• 第 $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$。