Basil's Garden
Contest: EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)
Difficulty rating: 1200
Tags: dp, greedy

There are $$$n$$$ flowers in a row, the $$$i$$$-th of them initially has a positive height of $$$h_i$$$ meters.

Every second, the wind will blow from the left, causing the height of some flowers to decrease.

Specifically, every second, for each $$$i$$$ from $$$1$$$ to $$$n$$$, in this order, the following happens:

- If $$$i = n$$$ or $$$h_i > h_{i + 1}$$$, the value of $$$h_i$$$ changes to $$$\max(0, h_i - 1)$$$.

How many seconds will pass before $$$h_i=0$$$ for all $$$1 \le i \le n$$$ for the first time?

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of flowers.

The second line of each test case contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10 ^ 9$$$) — the heights of the flowers.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output a single integer — the number of seconds that will pass before $$$h_i=0$$$ for all $$$1 \le i \le n$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the flower heights change as follows: $$$[1, 1, 2] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0]$$$.

In the second test case, the flower heights change as follows: $$$[3, 1] \rightarrow [2, 0] \rightarrow [1, 0] \rightarrow [0, 0]$$$.

Example input:
4
3
1 1 2
2
3 1
1
9
5
7 4 4 3 2

Example output:
4
3
9
7

Editorial:
First, let's try to find when $$$h_{n}$$$ will first be equal to zero. The answer is clearly $$$h_{n}$$$.
Suppose for some $$$2 \le i \le n$$$ we know that $$$h_{i}$$$ will first become equal to zero at time $$$t_{i}$$$ ($$$t_n = h_n$$$). If at some point in time, $$$h_{i-1}$$$ was equal to $$$h_{i}$$$ (at the start of the second and before they are both equal to zero), $$$t_{i-1}$$$ is equal to $$$t_{i} + 1$$$. Since after that point in time, if $$$h_{i}$$$ decreases, $$$h_{i-1}$$$ must decrease in the next second. If $$$h_{i-1}$$$ is never equal to $$$h_{i}$$$ (until they hit zero), $$$h_{i - 1}$$$ must always be strictly greater than $$$h_{i}$$$. This means that $$$h_{i-1}$$$ will keep decreasing every second until it hits zero, so $$$t_{i-1}$$$ is equal to $$$h_{i-1}$$$ in this case.
Examples:
• The array $$$[2, 3, 1, 1, 1]$$$ changes as follows: $$$[2, \color{red}{3}, 1, 1, \color{red}{1}] \rightarrow [2, \color{red}{2}, 1, \color{red}{1}, 0] \rightarrow [\color{red}{2}, 1, \color{red}{1}, 0, 0] \rightarrow$$$ $$$[1, \color{red}{1}, 0, 0, 0] \rightarrow [\color{red}{1}, 0, 0, 0, 0] \rightarrow [0, 0, 0, 0, 0]$$$. If we focus on the first two elements, they change as follows: $$$[2, \color{red}{3}] \rightarrow [2, \color{red}{2}] \rightarrow [\color{red}{2}, 1] \rightarrow [1, 1] \rightarrow [1, \color{red}{1}] \rightarrow [\color{red}{1}, 0] \rightarrow [0, 0]$$$.
• The array $$$[4, 1, 1]$$$ changes as follows: $$$[\color{red}{4}, 1, \color{red}{1}] \rightarrow [\color{red}{3}, \color{red}{1}, 0] \rightarrow [\color{red}{2}, 0, 0] \rightarrow [\color{red}{1}, 0, 0] \rightarrow [0, 0, 0]$$$.
Let's combine the two cases. If initially $$$h_{i-1} \le h_{i}$$$ holds, $$$h_{i-1}$$$ will become equal to $$$h_{i}$$$ at some point in time, so $$$t_{i-1} = t_{i} + 1$$$. Else, $$$h_{i-1} > h_{i}$$$, so $$$t_{i-1} = h_{i-1}$$$. Combining the two, we get $$$t_{i-1} = \max(h_{i-1}, t_{i} + 1)$$$.
Since we know $$$t_n = h_n$$$, we can easily calculate all the other values of $$$t_i$$$ by iterating from $$$n - 1$$$ to $$$1$$$. The answer to the problem is $$$t_1$$$, since $$$t_{i-1} \ge t_{i} + 1$$$ for all $$$2 \le i \le n$$$.
Complexity: $$$\mathcal{O}(n)$$$