CF1784C Monsters (hard version)

在一款电脑游戏中，你正在与 $n$ 个怪物作战。怪物 $i$ 的生命值为 $a_i$，所有的 $a_i$ 都是整数。只要怪物的生命值至少为 $1$，它就活着。 你可以施放两种类型的法术： 1. 对任意一个存活的怪物造成 $1$ 点伤害。 2. 对所有存活的怪物造成 $1$ 点伤害。如果至少有一个怪物死亡（其生命值降到 $0$），则该法术会继续重复施放，直到没有怪物死亡为止。 对怪物造成 $1$ 点伤害会减少其生命值 $1$ 点。 类型 $1$ 的法术可以施放任意次数，而类型 $2$ 的法术只能施放一次。 对于每个 $k = 1, 2, \dots, n$，请回答以下问题：假设游戏中只有前 $k$ 个怪物（编号为 $1, 2, \dots, k$）存在，那么最少需要施放多少次类型 $1$ 的法术才能击杀所有这 $k$ 个怪物？

- 第一行包含一个整数 $t$，表示测试用例的数量（$1 \le t \le 10^4$）。 - 接下来是 $t$ 个测试用例。每个测试用例包含两行： - 第一行包含一个整数 $n$，表示怪物的数量（$1 \le n \le 2 \times 10^5$）。 - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个怪物的生命值（$1 \le a_i \le n$）。 可以保证所有测试用例的 $n$ 总和不超过 $2 \times 10^5$。

对于每个测试用例，输出 $n$ 个整数，第 $k$ 个整数表示如果游戏中只存在前 $k$ 个怪物，最少需要施放多少次类型 $1$ 的法术来击杀所有这些怪物。

#### 示例 1 在第一个测试用例中，当 $k = n$ 时，怪物的初始生命值为 $[3, 1, 2]$。此时只需要施放一次类型 $2$ 的法术： - 使用类型 $2$ 法术，对所有怪物造成 $1$ 点伤害，怪物的生命值变为 $[2, 0, 1]$。由于怪物 $2$ 死亡，法术会继续施放。 - 使用类型 $2$ 法术，怪物的生命值变为 $[1, 0, 0]$，此时怪物 $3$ 死亡，法术继续施放。 - 使用类型 $2$ 法术，怪物的生命值变为 $[0, 0, 0]$，此时怪物 $1$ 死亡，法术继续施放。 - 使用类型 $2$ 法术，所有怪物的生命值都降为 $0$，结束。 因此，最后无需再使用类型 $1$ 法术，答案是 $0$ 次。 #### 示例 2 在第二个测试用例中，怪物的初始生命值为 $[4, 1, 5, 4, 1, 1]$。一种最优的行动顺序如下： - 先使用类型 $1$ 法术，给怪物 $1$ 造成 $1$ 点伤害，生命值变为 $[3, 1, 5, 4, 1, 1]$。 - 再使用类型 $1$ 法术，给怪物 $4$ 造成 $1$ 点伤害，生命值变为 $[3, 1, 5, 3, 1, 1]$。 - 再使用类型 $1$ 法术，给怪物 $4$ 造成 $1$ 点伤害，生命值变为 $[3, 1, 5, 2, 1, 1]$。 - 然后使用类型 $2$ 法术： - 所有怪物的生命值减去 $1$，变为 $[2, 0, 4, 1, 0, 0]$，怪物 $2$、$5$ 和 $6$ 死亡，法术继续施放。 - 再次使用类型 $2$ 法术，怪物的生命值变为 $[1, 0, 3, 0, 0, 0]$，怪物 $4$ 死亡，法术继续施放。 - 再次使用类型 $2$ 法术，怪物的生命值变为 $[0, 0, 2, 0, 0, 0]$，怪物 $1$ 死亡，法术继续施放。 - 使用类型 $2$ 法术，怪物的生命值变为 $[0, 0, 1, 0, 0, 0]$。 - 然后使用类型 $1$ 法术，给怪物 $3$ 造成 $1$ 点伤害，生命值变为 $[0, 0, 0, 0, 0, 0]$，结束。 因此，总共需要施放 $4$ 次类型 $1$ 法术。