310811: CF1891C. Smilo and Monsters

C. Smilo and Monsterstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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}$.

Output

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

ExampleInput

4
4
1 3 1 1
4
1 2 1 1
6
3 2 1 5 2 4
2
1 6

Output

4
4
11
5

Note

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.

题目大意：
一个名为Smilo的男孩在玩一个新游戏！游戏中总共有n波怪物，第i波有a_i个怪物。游戏的目标是摧毁所有怪物。为了做到这一点，你有两种类型的攻击和一个连击计数器x，最初设置为0：
1. 第一种类型：你从1到n选择一个数字i，使得第i波中至少剩下一个怪物。然后，你杀死第i波的一个怪物，连击计数器x增加1。
2. 第二种类型：你从1到n选择一个数字i，使得第i波中至少剩下x个怪物。然后，你使用一个终极攻击并杀死第i波的x个怪物。之后，x重置为0。
你的任务是摧毁所有怪物，这意味着任何一波中都不应该剩下怪物。Smilo想尽快赢，所以他想知道赢得游戏所需的最少攻击次数。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——怪物的波数。
第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9）——每波中怪物的数量。
保证所有测试用例中n的总和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出摧毁所有怪物所需的最少攻击次数。

例：
输入
```
4
4
1 3 1 1
4
1 2 1 1
6
3 2 1 5 2 4
2
1 6
```
输出
```
4
4
11
5
```
注意：
- 在第一个测试用例中，我们可以对第1、3和4波使用第一种攻击，然后对第2波使用第二种攻击。总共需要4次攻击。
- 在第二个测试用例中，我们可以对第1和3波使用第一种攻击，然后对第2波使用第二种攻击，最后对第4波使用第一种攻击。总共需要4次攻击。
- 在第四个测试用例中，我们可以对第1波使用第一种攻击一次，对第2波使用两次，然后对第2波使用第二种攻击，最后对第2波使用第一种攻击。总共需要5次攻击。题目大意： 一个名为Smilo的男孩在玩一个新游戏！游戏中总共有n波怪物，第i波有a_i个怪物。游戏的目标是摧毁所有怪物。为了做到这一点，你有两种类型的攻击和一个连击计数器x，最初设置为0： 1. 第一种类型：你从1到n选择一个数字i，使得第i波中至少剩下一个怪物。然后，你杀死第i波的一个怪物，连击计数器x增加1。 2. 第二种类型：你从1到n选择一个数字i，使得第i波中至少剩下x个怪物。然后，你使用一个终极攻击并杀死第i波的x个怪物。之后，x重置为0。 你的任务是摧毁所有怪物，这意味着任何一波中都不应该剩下怪物。Smilo想尽快赢，所以他想知道赢得游戏所需的最少攻击次数。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——怪物的波数。 第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9）——每波中怪物的数量。 保证所有测试用例中n的总和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出摧毁所有怪物所需的最少攻击次数。 例： 输入 ``` 4 4 1 3 1 1 4 1 2 1 1 6 3 2 1 5 2 4 2 1 6 ``` 输出 ``` 4 4 11 5 ``` 注意： - 在第一个测试用例中，我们可以对第1、3和4波使用第一种攻击，然后对第2波使用第二种攻击。总共需要4次攻击。 - 在第二个测试用例中，我们可以对第1和3波使用第一种攻击，然后对第2波使用第二种攻击，最后对第4波使用第一种攻击。总共需要4次攻击。 - 在第四个测试用例中，我们可以对第1波使用第一种攻击一次，对第2波使用两次，然后对第2波使用第二种攻击，最后对第2波使用第一种攻击。总共需要5次攻击。