1987C.md (1721B)
1 Source: https://codeforces.com/problemset/problem/1987/C 2 3 C. Basil's Garden 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There are $n$ flowers in a row, the $i$-th of them initially has a positive height of $h_i$ meters. 22 23 Every second, the wind will blow from the left, causing the height of some flowers to decrease. 24 25 Specifically, every second, for each $i$ from $1$ to $n$, in this order, the following happens: 26 27 * If $i = n$ or $h_i \gt h_{i + 1}$, the value of $h_i$ changes to $\max(0, h_i - 1)$. 28 29 How many seconds will pass before $h_i=0$ for all $1 \le i \le n$ for the first time? 30 31 Input 32 33 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. 34 35 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of flowers. 36 37 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. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 40 41 Output 42 43 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$. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 3 53 54 1 1 2 55 56 2 57 58 3 1 59 60 1 61 62 9 63 64 5 65 66 7 4 4 3 2 67 ``` 68 69 Output 70 71 ``` 72 4 73 3 74 9 75 7 76 ``` 77 78 Note 79 80 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]$. 81 82 In the second test case, the flower heights change as follows: $[3, 1] \rightarrow [2, 0] \rightarrow [1, 0] \rightarrow [0, 0]$.