C. Сад Бейзила
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть ряд из $$$n$$$ цветов, у $$$i$$$-го из них изначально высота $$$h_i$$$ метров.

Каждую секунду порыв ветра слева будет понижать высоты некоторых цветов.

А именно, каждую секунду, для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ в этом порядке, происходит следующее:

  • Если $$$i = n$$$ или $$$h_i > h_{i + 1}$$$, значение $$$h_i$$$ меняется на $$$\max(0, h_i - 1)$$$.

Сколько секунд пройдёт перед тем, как $$$h_i=0$$$ будет впервые верно для всех $$$1 \le i \le n$$$?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных, выведите одно целое число — количество секунд, которое пройдёт перед тем, как $$$h_i=0$$$ будет впервые верно для всех $$$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
Примечание

В первом наборе входных данных высоты цветов меняются следующим образом: $$$[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]$$$.