E. Всё съехало
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Юсефа есть $$$n$$$ столбцов кубиков, стоящих рядом друг с другом. $$$i$$$-й столбец содержит $$$a_i$$$ одинаковых единичных кубиков, сложенных вертикально. Изначально гравитация тянет кубики вниз, поэтому каждый столбец $$$i$$$ содержит ровно $$$a_i$$$ кубиков на высотах $$$1, 2, \dots, a_i$$$.

Внезапно гравитация меняет направление и начинает тянуть вправо. Каждый кубик скользит горизонтально как можно дальше вправо. Кубик не может проходить сквозь другие кубики или накладываться на них, и он должен оставаться на своей исходной высоте. Итоговая конфигурация однозначно определяется начальными высотами.

До и после изменения направления гравитации вправо.

Перед изменением гравитации Юсеф может выполнить не более одной операции: выбрать индекс $$$i$$$ и уменьшить $$$a_i$$$ на $$$1$$$ (то есть убрать один кубик из этого столбца). Он также может ничего не делать.

Скажем, что кубик двигается, если после изменения направления гравитации индекс его столбца отличается от исходного индекса столбца.

Найдите максимальное возможное количество кубиков, которые будут двигаться после изменения направления гравитации, если Юсеф оптимально применит единственное уменьшение (или решит не применять его).

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

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — максимальное возможное количество кубиков, которые будут двигаться после изменения направления гравитации, если Юсеф оптимально применит единственное уменьшение (или решит не применять его).

Пример
Входные данные
5
5
1 2 3 2 1
7
5 4 1 1 1 1 3
6
1 2 3 4 5 6
6
4 1 6 3 2 6
7
1 3 2 7 2 3 1
Выходные данные
8
12
0
10
18
Примечание

В первом наборе входных данных оптимально выполнить операцию с индексом $$$5$$$ и получить массив $$$a = [1, 2, 3, 2, 0]$$$. После изменения направления гравитации двигаться будут все оставшиеся кубики. Ответ равен $$$1+2+3+2 = 8$$$. Можно доказать, что большего ответа не существует.

Во втором наборе входных данных можно выполнить операцию с индексом $$$6$$$ и получить массив $$$a = [5, 4, 1, 1, 1, 0, 3]$$$. После изменения направления гравитации будут двигаться $$$5+4+1+1+1 = 12$$$ кубиков. Заметьте, что кубики в позиции $$$7$$$ не двигаются, поскольку они уже находятся у правого края массива.

В третьем наборе входных данных невозможно заставить двигаться хотя бы один кубик.