题目描述

字节镇刚举办了一场盛大的《字节：比特明翰》（Bajt: Bitmingham）游戏锦标赛。每场对局正好需要三名玩家，他们得聚在同一个地方才能开赛。

你可能早就知道，字节镇只有一条长街，沿街有 $n$ 栋建筑，编号从 $1$ 到 $n$。

为了方便玩家，规则定下：如果三位玩家住在编号为 $a,b,c$ 的建筑，对局就在中间那栋举行，也就是编号为 $a,b,c$ 中位数的建筑。特别地，若两位玩家住在同一栋 $x$ 号建筑，无论第三位住哪，对局都在 $x$ 号建筑进行。

你正在整理锦标赛的统计数据。你知道每组三人最多对战一次，并且清楚每栋建筑举办的对局数：第 $i$ 栋有 $a_{i}$ 场对局。可惜，你忘了查有多少玩家参加了锦标赛……

请你算出，与已有信息不矛盾的最小玩家人数。

你需要为 $t$ 组独立测试数据解决这个问题。

输入格式

输入的第一行包含一个整数 $t$ $(1 \leq t \leq 50)$，表示测试数据数量。

每组测试数据占两行。第一行是一个整数 $n$ $(1 \leq n \leq 200000)$，表示字节镇的建筑数量。第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$ $(0 \leq a_{i} \leq 1000000)$，表示每栋建筑举办的对局数。保证至少一个 $a_{i}$ 为正数。

所有测试数据的 $n$ 之和不超过 $200000$。

输出格式

输出 $t$ 行，每行一个整数，表示第 $i$ 组测试数据中可能参加锦标赛的最小玩家人数。

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

3
9
5
6

在第一组测试数据中，一场对局需要 $3$ 个玩家。
在第二组测试数据中，有 $57$ 场对局；$8$ 个玩家不够，因为只能组成 $\binom{8}{3}=56$ 个不同三人组，所以需要第 $9$ 个玩家。
在第三组测试数据中，每栋建筑可以各住一个玩家：

• 第 $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$ 号玩家的对战。
  在第四组测试数据中，$5$ 个玩家不够，因为某栋建筑最多只有 $2$ 人，凑不出 $4$ 个符合中位数条件的三人组。