P14589 [LNCPC 2025] 子鼠

Z 形管道猫正在研究如何高效发动《三国杀》中的“子鼠”。

子鼠：技能，您可以选择一名卡牌数大于您的其他角色，然后获得其的一张卡牌。 总共有 $n$ 名角色，您是第 $1$ 名角色。初始，第 $i$ 名角色有 $a_i$ 张卡牌。 请您求出只通过您发动任意次（可以零次）“子鼠”后，您的卡牌数的最大值。

每个测试点包含多组测试数据。第一行给定一个整数 $T(1\le T\le 10^4)$，表示测试数据组数。 对于每组测试数据：\ 第一行给定一个整数 $n(1\le n\le10^6)$，表示角色数。\ 第二行给定 $n$ 个整数 $a_i(0\le a_i\le10^9)$，其中第 $i$ 个整数 $a_i$ 表示初始第 $i$ 名角色的卡牌数。 保证在每个测试点中所有测试数据的 $n$ 的总和不超过 $10^6$。

对于每组测试数据，输出一行一个整数，表示只通过您发动任意次“子鼠”后，您的卡牌数的最大值。

对于样例的第一组测试数据： 您发动第一次“子鼠”：选择第 $2$ 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 $\textbf{\color{red}1},\textbf{\color{red}2},1$。 您发动第二次“子鼠”：选择第 $2$ 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 $\textbf{\color{red}2},\textbf{\color{red}1},1$。 因为此时没有卡牌数大于您的其他角色，所以您无法发动第三次“子鼠”。 可以证明，只通过您发动任意次“子鼠”后，您的卡牌数的最大值是 $2$。 对于样例的第二组测试数据： 您发动第一次“子鼠”：选择第 $3$ 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 $\textbf{\color{red}1},2,\textbf{\color{red}2},0$。 您发动第二次“子鼠”：选择第 $2$ 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 $\textbf{\color{red}2},\textbf{\color{red}1},2,0$。 因为此时没有卡牌数大于您的其他角色，所以您无法发动第三次“子鼠”。 可以证明，只通过您发动任意次“子鼠”后，您的卡牌数的最大值是 $2$。