← 返回题目列表

Codeforces · 2133/D

D. 鸡骑师

中文机器翻译题面 查看原题

史蒂夫做出了一个愚蠢的决定,在晚上采矿,并遇到了一种可怕的生物: 鸡骑师$$$^n$$$!

鸡骑师$$$^n$$$ 由$$$n$$$ 生物按顺序堆叠在一起组成,生物$$$1$$$ 在底部,生物$$$n$$$ 在顶部。生物 $$$i$$$ 最初拥有 $$$h_i$$$ 生命值。

在一次攻击中,史蒂夫可以对任何生物造成 $$$1$$$ 伤害。如果任何生物的生命值达到 $$$0$$$ 或更低,它就会死亡,并且其上的所有生物都会倒下并形成一个 新 堆栈。的 底部 新堆栈中的生物在掉落之前对其上方的每个生物都会造成 $$$1$$$ 掉落伤害(即前一堆栈中位于其下方的生物数量,包括刚刚死亡的生物)。这也可能会杀死它,在这种情况下,它上面的所有小怪都会再次掉落并重复该过程。

例如,考虑一个鸡骑师$$$^6$$$,其初始生物生命值为$$$[1, 2, 1, 3, 5, 2]$$$。如果史蒂夫伤害了堆叠中的第三个生物,它就会死亡,并且生命值为 $$$[3, 5, 2]$$$ 的生物会落入新的堆叠中。底部的生物受到 $$$3$$$ 单位的坠落伤害,因此它也会死亡,而生命值 $$$[5, 2]$$$ 的生物会在新的堆栈中掉落。底部的生物承受 $$$1$$$ 单位的坠落伤害。因此,在 Steve 第一次攻击后,将会有两个生命值分别为 $$$[1, 2]$$$ 和 $$$[4, 2]$$$ 的堆栈。

史蒂夫的剑的耐用性很低,所以他想知道杀死所有小怪所需的最低攻击次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 生物数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2,\ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) - 每个生物的初始生命值。

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

输出

对于每个测试用例,输出一个整数 - 杀死所有小怪所需的最少攻击。

示例

输入
复制

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

输出
复制

7
1
7
5
2999999998

注意

在第一个测试用例中,初始堆栈中的生物的生命值为 $$$[3, 1, 4, 1, 2]$$$。史蒂夫可以使用一次攻击来伤害堆栈中的第二个生物并将其杀死。第三个生物受到 $$$2$$$ 单位的坠落伤害。现在有两个堆栈:$$$[3]$$$ 和 $$$[2, 1, 2]$$$。现在史蒂夫可以杀死第二堆中的第二个生物。堆叠中的第三个生物受到 $$$2$$$ 单位的坠落伤害,将其杀死。现在有两个堆栈:$$$[3]$$$ 和 $$$[2]$$$。最后,史蒂夫可以使用五次攻击来杀死剩下的小怪。

在第二个测试用例中,Steve 可以对堆栈中底部的生物造成 $$$1$$$ 伤害。当它死亡时,第二个生物将承受 $$$1$$$ 单位的坠落伤害并死亡;那么第三个生物将受到 $$$1$$$ 单位的坠落伤害并死亡;最后,第四个生物将承受 $$$1$$$ 单位的坠落伤害并死亡。