CF2133D.Chicken Jockey

Steve 做出了一个愚蠢的决定，在夜晚进行挖矿，结果遇到了一种可怕的生物：chicken jockey$$^n$$！

一个 chicken jockey$$^n$$ 由 $$n$$ 个生物依次叠在一起组成，第 $$$1$$$ 个生物在最底层，第 $$$n$$$ 个生物在最顶层。第 $$$i$$$ 个生物初始拥有 $$$h_i$$$ 点生命值。

每次攻击，Steve 可以对任意一个生物造成 $1$ 点伤害。如果某个生物的生命值降到 $0$ 或更低，则它会死亡，其上方的所有生物会掉落下来，重新组成一个新的堆叠。新堆叠中最底层的生物会因为掉落受到等于它之前下方生物数量（包括刚刚死亡的那个）的 $1$ 点掉落伤害。如果这也导致它死亡，则其上方的所有生物再次掉落，过程重复进行。

例如，考虑一个初始生命值为 $[1, 2, 1, 3, 5, 2]$ 的 chicken jockey$^6$。如果 Steve 攻击堆叠中的第三个生物，它会死亡，生命值为 $[3, 5, 2]$ 的生物会掉落组成新堆叠。新堆叠的最底层生物会受到 $3$ 点掉落伤害，因此也会死亡，生命值为 $[5, 2]$ 的生物再次掉落组成新堆叠。新堆叠的最底层生物会受到 $1$ 点掉落伤害。最终，Steve 第一次攻击后，会剩下两个堆叠，生命值分别为 $[1, 2]$ 和 $[4, 2]$。

Steve 的剑耐久度很低，他想知道消灭所有生物所需的最少攻击次数。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。

每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示生物的数量。

每组测试数据的第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$1 \le h_i \le 10^9$），表示每个生物的初始生命值。

保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出一个整数，表示消灭所有生物所需的最少攻击次数。

在第一个测试用例中，初始堆叠的生物生命值为 $[3, 1, 4, 1, 2]$。Steve 可以用一次攻击击杀堆叠中的第二个生物。第三个生物会受到 $2$ 点掉落伤害。现在有两个堆叠：$[3]$ 和 $[2, 1, 2]$。接着 Steve 可以击杀第二个堆叠中的第二个生物，第三个生物会受到 $2$ 点掉落伤害并死亡。现在有两个堆叠：$[3]$ 和 $[2]$。最后，Steve 需要用五次攻击击杀剩下的生物。

在第二个测试用例中，Steve 可以对堆叠最底层的生物造成 $1$ 点伤害。当它死亡时，第二个生物会受到 $1$ 点掉落伤害并死亡；接着第三个生物会受到 $1$ 点掉落伤害并死亡；最后第四个生物会受到 $1$ 点掉落伤害并死亡。

由 ChatGPT 4.1 翻译