连续有 $$$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]$$$。