CF1987C Basil's Garden

题目描述

有 $n$ 朵花排成一排，第 $i$ 朵花的初始高度为 $h_i$ 米，且 $h_i$ 为正整数。

每一秒，风会从左边吹来，使得某些花的高度减少。

具体来说，每一秒，对于每个 $i$ 从 $1$ 到 $n$，按顺序执行以下操作：

• 如果 $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

输入 #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]$。

由 ChatGPT 4.1 翻译