这是问题的困难版本。在这个版本中,你需要为怪物数组的每个前缀找到答案。
在电脑游戏中,您正在与 $$$n$$$ 怪物战斗。怪物编号$$$i$$$有$$$a_i$$$生命值,所有$$$a_i$$$都是整数。怪物在生命值至少为 $$$1$$$ 时仍存活。
你可以施展两种类型的法术:
1. 对你选择的任何单个活着的怪物造成 $$$1$$$ 伤害。
2. 对所有活着的怪物造成 $$$1$$$ 伤害。如果此操作导致至少一只怪物死亡(最终获得 $$$0$$$ 生命值),则重复该操作(每次至少有一只怪物死亡时继续重复)。
对怪物造成 $$$1$$$ 伤害,使其生命值降低 $$$1$$$。
类型 1 的法术可以施展任意次数,而类型 2 的法术在游戏中最多可以施展一次。
对于每个 $$$k = 1, 2, \ldots, n$$$,回答以下问题。假设游戏中仅存在前 $$$k$$$ 怪物,编号为 $$$1、2、\ldots、k$$$。杀死所有 $$$k$$$ 怪物需要施展 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$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数。如果游戏中仅存在编号为 $$$1, 2, \ldots, k$$$ 的怪物,则这些整数中的第 $$$k$$$ 必须等于您需要施放类型 1 的法术来杀死所有 $$$k$$$ 怪物的最小次数。
示例
输入 #1
2 3 3 1 2 6 4 1 5 4 1 1
输出 #1
2 1 0 3 2 4 4 4 4
注意
在第一个测试用例中,对于$$$k = n$$$,怪物的初始生命值是$$$[3, 1, 2]$$$。施展类型 2 的咒语就足够了:
- 怪物的生命值变为 $$$[2, 0, 1]$$$。由于编号 $$$2$$$ 的怪物死亡,该咒语会重复。
- 怪物的生命值更改为 $$$[1, 0, 0]$$$。由于编号 $$$3$$$ 的怪物死亡,该咒语会重复。
- 怪物的生命值更改为 $$$[0, 0, 0]$$$。由于编号 $$$1$$$ 的怪物死亡,该咒语会重复。
- 怪物的生命值变为 $$$[0, 0, 0]$$$。
由于根本不可能使用类型 1 的法术,答案是 $$$0$$$。
在第二个测试用例中,对于 $$$k = n$$$,怪物的初始生命值是 $$$[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 的法术:怪物的生命值变为 $$$[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$$$ 次。可以证明这是最小的可能数。