Monsters (easy version)
Contest: VK Cup 2022 - Финальный раунд (Engine)
Difficulty rating: 1000
Tags: brute force, greedy

This is the easy version of the problem. In this version, you only need to find the answer once. In this version, hacks are not allowed.

In a computer game, you are fighting against $$$n$$$ monsters. Monster number $$$i$$$ has $$$a_i$$$ health points, all $$$a_i$$$ are integers. A monster is alive while it has at least $$$1$$$ health point.

You can cast spells of two types:

1. Deal $$$1$$$ damage to any single alive monster of your choice.
2. Deal $$$1$$$ damage to all alive monsters. If at least one monster dies (ends up with $$$0$$$ health points) as a result of this action, then repeat it (and keep repeating while at least one monster dies every time).

Dealing $$$1$$$ damage to a monster reduces its health by $$$1$$$.

Spells of type 1 can be cast any number of times, while a spell of type 2 can be cast at most once during the game.

What is the smallest number of times you need to cast spells of type 1 to kill all monsters?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of monsters.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — monsters' health points.

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

Output format:
For each test case, print a single integer — the smallest number of times you need to cast spells of type 1 to kill all monsters.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the initial health points of the monsters are $$$[3, 1, 2]$$$. It is enough to cast a spell of type 2:

- Monsters' health points change to $$$[2, 0, 1]$$$. Since monster number $$$2$$$ dies, the spell is repeated.
- Monsters' health points change to $$$[1, 0, 0]$$$. Since monster number $$$3$$$ dies, the spell is repeated.
- Monsters' health points change to $$$[0, 0, 0]$$$. Since monster number $$$1$$$ dies, the spell is repeated.
- Monsters' health points change to $$$[0, 0, 0]$$$.

Since it is possible to use no spells of type 1 at all, the answer is $$$0$$$.

In the second test case, the initial health points of the monsters are $$$[4, 1, 5, 4, 1, 1]$$$. Here is one of the optimal action sequences:

- Using a spell of type 1, deal $$$1$$$ damage to monster number $$$1$$$. Monsters' health points change to $$$[3, 1, 5, 4, 1, 1]$$$.
- Using a spell of type 1, deal $$$1$$$ damage to monster number $$$4$$$. Monsters' health points change to $$$[3, 1, 5, 3, 1, 1]$$$.
- Using a spell of type 1, deal $$$1$$$ damage to monster number $$$4$$$ again. Monsters' health points change to $$$[3, 1, 5, 2, 1, 1]$$$.
- Use a spell of type 2:  Monsters' health points change to $$$[2, 0, 4, 1, 0, 0]$$$. Since monsters number $$$2$$$, $$$5$$$, and $$$6$$$ die, the spell is repeated.  Monsters' health points change to $$$[1, 0, 3, 0, 0, 0]$$$. Since monster number $$$4$$$ dies, the spell is repeated.  Monsters' health points change to $$$[0, 0, 2, 0, 0, 0]$$$. Since monster number $$$1$$$ dies, the spell is repeated.  Monsters' health points change to $$$[0, 0, 1, 0, 0, 0]$$$.
- Using a spell of type 1, deal $$$1$$$ damage to monster number $$$3$$$. Monsters' health points change to $$$[0, 0, 0, 0, 0, 0]$$$.

Spells of type 1 are cast $$$4$$$ times in total. It can be shown that this is the smallest possible number.

Example input:
2
3
3 1 2
6
4 1 5 4 1 1

Example output:
0
4

Editorial:
First, let's prove that it's always optimal to use a spell of type 2 as your last spell in the game and kill all monsters with it. Indeed, suppose you use a spell of type 2 earlier and it deals $$$x$$$ damage to all monsters. Suppose that some monsters are still alive. For any such monster, say they had $$$y$$$ health points before the spell of type 2, and $$$y > x$$$. Then, you will need to cast $$$y-x$$$ more spells of type 1 to kill it afterwards. But you could just cast these $$$y-x$$$ spells of type 1 on this monster before casting the spell of type 2. Thus, you can move all usages of spells of type 1 before the usage of the spell of type 2 without changing the answer.
Without loss of generality, assume that $$$a_1 \le a_2 \le \ldots \le a_n$$$. Let $$$b_i$$$ be the amount of health points monster $$$i$$$ has right before the spell of type 2 is cast ($$$1 \le b_i \le a_i$$$). Then, the number of spells of type 1 needed is $$$\sum \limits_{i=1}^n (a_i - b_i)$$$, which means we want to maximize $$$\sum \limits_{i=1}^n b_i$$$.
Note that we can rearrange $$$b$$$ so that $$$b_1 \le b_2 \le \ldots \le b_n$$$: since $$$a$$$ is sorted too, the $$$b_i \le a_i$$$ condition will still hold.
Also, since all monsters must be killed by a spell of type 2 afterwards, $$$b_{i+1} - b_i \le 1$$$ must hold.
Thus, we should go through all monsters in non-decreasing order of $$$a_i$$$ and decide their $$$b_i$$$ greedily, picking the largest value satisfying both $$$b_i \le a_i$$$ and $$$b_i \le b_{i-1} + 1$$$. Specifically, we should choose $$$b_1 = 1$$$ and $$$b_i = \min(a_i, b_{i-1} + 1)$$$.