题目描述

这是该问题的简单版本。在这个版本中，你只需要找到一次答案。在这个版本中，不允许 hack。

在一款电脑游戏中，你正在与 $n$ 个怪物战斗。第 $i$ 个怪物有 $a_i$ 点生命值，所有 $a_i$ 都是整数。当怪物的生命值至少为 $1$ 时，它仍然存活。

你可以施放两种类型的法术：

1. 对任意一个存活的怪物造成 $1$ 点伤害。
2. 对所有存活的怪物各造成 $1$ 点伤害。如果至少有一个怪物因此死亡（生命值变为 $0$），则该法术会被重复施放（只要每次施放后至少有一个怪物死亡，就继续重复）。

对怪物造成 $1$ 点伤害会使其生命值减少 $1$。

类型 1 的法术可以施放任意多次，而类型 2 的法术在游戏中最多只能施放一次。

你需要施放多少次类型 1 的法术，才能杀死所有怪物？请输出最小次数。

输入格式

每组测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例包含两行。第一行是一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示怪物的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示每个怪物的生命值。

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

输出格式

对于每个测试用例，输出一个整数，表示杀死所有怪物所需施放类型 1 法术的最小次数。

说明/提示

在第一个测试用例中，怪物的初始生命值为 $[3, 1, 2]$。只需施放一次类型 2 法术即可：

• 怪物生命值变为 $[2, 0, 1]$。由于第 2 只怪物死亡，法术被重复施放。
• 怪物生命值变为 $[1, 0, 0]$。由于第 3 只怪物死亡，法术被重复施放。
• 怪物生命值变为 $[0, 0, 0]$。由于第 1 只怪物死亡，法术被重复施放。
• 怪物生命值变为 $[0, 0, 0]$。

因此，可以不施放任何类型 1 法术，答案为 $0$。

在第二个测试用例中，怪物的初始生命值为 $[4, 1, 5, 4, 1, 1]$。以下是一种最优操作序列：

• 施放一次类型 1 法术，对第 1 只怪物造成 $1$ 点伤害。怪物生命值变为 $[3, 1, 5, 4, 1, 1]$。
• 施放一次类型 1 法术，对第 4 只怪物造成 $1$ 点伤害。怪物生命值变为 $[3, 1, 5, 3, 1, 1]$。
• 再次对第 4 只怪物施放一次类型 1 法术。怪物生命值变为 $[3, 1, 5, 2, 1, 1]$。
• 施放一次类型 2 法术：
  • 怪物生命值变为 $[2, 0, 4, 1, 0, 0]$。由于第 2、5、6 只怪物死亡，法术被重复施放。
  • 怪物生命值变为 $[1, 0, 3, 0, 0, 0]$。由于第 4 只怪物死亡，法术被重复施放。
  • 怪物生命值变为 $[0, 0, 2, 0, 0, 0]$。由于第 1 只怪物死亡，法术被重复施放。
  • 怪物生命值变为 $[0, 0, 1, 0, 0, 0]$。
• 施放一次类型 1 法术，对第 3 只怪物造成 $1$ 点伤害。怪物生命值变为 $[0, 0, 0, 0, 0, 0]$。

类型 1 法术一共施放了 $4$ 次。可以证明这是最小次数。

由 ChatGPT 4.1 翻译

样例

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

0
4