← 返回题目列表

Codeforces · 1987/C

C. 巴兹尔花园

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

连续有 $$$n$$$ 朵花,其中第 $$$i$$$ 最初的正高度为 $$$h_i$$$ 米。

每一秒,风都会从左边吹来,导致一些花的高度降低。

具体来说,每秒,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,按此顺序发生以下情况:

- 如果 $$$i = n$$$ 或 $$$h_i > h_{i + 1}$$$,则 $$$h_i$$$ 的值更改为 $$$\max(0, h_i - 1)$$$。

对于所有 $$$1 \le i \le n$$$ 第一次,$$$h_i=0$$$ 之前需要经过多少秒?

输入

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

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10 ^ 9$$$) — 花的高度。

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

输出

对于每个测试用例,输出一个整数 - 对于所有 $$$1 \le i \le n$$$,$$$h_i=0$$$ 之前将经过的秒数。

示例

输入 #1

4
3
1 1 2
2
3 1
1
9
5
7 4 4 3 2

输出 #1

4
3
9
7

注意

在第一个测试用例中,花的高度变化如下:$$$[1, 1, 2] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0]$$$。

在第二个测试用例中,花高度变化如下:$$$[3, 1] \rightarrow [2, 0] \rightarrow [1, 0] \rightarrow [0, 0]$$$。