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

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

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

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

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

Расстояние перемещения кубика определяется как $$$|j - i|$$$, где $$$i$$$ — индекс его исходного столбца, а $$$j$$$ — индекс его столбца после изменения гравитации.

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

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

Первая строка содержит целое число $$$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
Выходные данные
9
37
0
17
29
Примечание

В первом наборе входных данных начальная суммарная длина перемещения равна $$$5$$$. Если Юсеф убирает кубик с индексом $$$5$$$, массив становится $$$[1, 2, 3, 2, 0]$$$. Поскольку пятый столбец теперь пуст, все кубики из первых четырёх столбцов могут скользить вправо дальше, чем могли изначально. Это даёт новую суммарную длину перемещения, равную $$$9$$$.

В третьем наборе входных данных начальная суммарная длина перемещения равна $$$0$$$. Даже если Юсеф уберёт любой кубик, ни один из оставшихся кубиков не сможет сдвинуться. В результате суммарная длина перемещения остаётся равной $$$0$$$.