CF1891C.Smilo and Monsters

A boy called Smilo is playing a new game! In the game, there are $n$ hordes of monsters, and the $i$-th horde contains $a_i$ monsters. The goal of the game is to destroy all the monsters. To do this, you have two types of attacks and a combo counter $x$, initially set to $0$:

• The first type: you choose a number $i$ from $1$ to $n$, such that there is at least one monster left in the horde with the number $i$. Then, you kill one monster from horde number $i$, and the combo counter $x$ increases by $1$.
• The second type: you choose a number $i$ from $1$ to $n$, such that there are at least $x$ monsters left in the horde with number $i$. Then, you use an ultimate attack and kill $x$ monsters from the horde with number $i$. After that, $x$ is reset to zero.

Your task is to destroy all of the monsters, meaning that there should be no monsters left in any of the hordes. Smilo wants to win as quickly as possible, so he wants to the minimum number of attacks required to win the game.

一个名叫斯米洛的男孩正在玩一款新游戏！游戏中有 $n$ 群怪物，其中第 $i$ 群包含 $a_i$ 只怪物。游戏的目标是消灭所有怪物。为此，你有两种攻击方式以及一个连击计数器 $x$（初始值为 $0$）：

• 第一种攻击：选择一个编号 $i$（$1 \le i \le n$），要求第 $i$ 群中至少还剩一只怪物；然后你消灭第 $i$ 群中的一只怪物，同时连击计数器 $x$ 增加 $1$。
• 第二种攻击：选择一个编号 $i$（$1 \le i \le n$），要求第 $i$ 群中至少还剩 $x$ 只怪物；然后你发动终极攻击，消灭第 $i$ 群中的 $x$ 只怪物；之后，$x$ 被重置为 $0$。

你的任务是消灭所有怪物，即所有群中都不再剩下任何怪物。斯米洛希望尽快获胜，因此他想知道赢得游戏所需的最少攻击次数。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The descriptions of the test cases follow.

The first line of each input data set contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of hordes of monsters.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the number of monsters in each horde.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot {10^5}$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。随后是各测试用例的描述。

每个输入数据集的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——怪物群的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）——每群怪物的数量。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, out put the minimum number of attacks required to kill all monsters.

对于每个测试用例，输出消灭所有怪物所需的最少攻击次数。

In the first test case, we can use an attack of the first type on the $1$-st, $3$-rd and $4$-th hordes, and then use an attack of the second type to finish off the $2$-nd horde. We need $4$ attacks in total.

In the second test case, we can use an attack of the first type on the $1$-st and $3$-rd hordes, then use an attack of the second type to finish off the $2$-nd horde, and then use an attack of the first type on the $4$-th horde. We need $4$ attacks in total.

In the fourth test case, we can use an attack of the first type once on the $1$-st horde, twice on the $2$-nd horde, and then use an attack of the second type on the $2$-nd horde, and finally use an attack of the first type to finish off the $2$-nd horde. We need $5$ attacks in total.

在第一个测试用例中，我们可以对第 $1$、第 $3$ 和第 $4$ 波敌军各使用一次第一类攻击，然后对第 $2$ 波敌军使用一次第二类攻击将其消灭。总共需要 $4$ 次攻击。

在第二个测试用例中，我们可以对第 $1$ 和第 $3$ 波敌军各使用一次第一类攻击，然后对第 $2$ 波敌军使用一次第二类攻击将其消灭，最后对第 $4$ 波敌军使用一次第一类攻击。总共需要 $4$ 次攻击。

在第四个测试用例中，我们可以对第 $1$ 波敌军使用一次第一类攻击，对第 $2$ 波敌军使用两次第一类攻击，然后对第 $2$ 波敌军使用一次第二类攻击，最后再对第 $2$ 波敌军使用一次第一类攻击将其消灭。总共需要 $5$ 次攻击。