Basil's Garden
Description
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?
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$.
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$.
Input
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
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$.
4
3
1 1 2
2
3 1
1
9
5
7 4 4 3 2
4
3
9
7
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]$.