C. Операция над подмассивом
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$a$$$ размера $$$n$$$.

Вы можете выполнить следующую операцию: выберите диапазон $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) и замените значения элементов $$$a_l, a_{l+1}, \dots, a_r$$$ на $$$(l + r)$$$.

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

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2n$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
3
2 5 1
2
4 4
4
1 3 2 1
5
3 2 0 9 10
Выходные данные
13
8
20
32
Примечание

В первом примере вы можете выполнить операцию на подмассиве $$$[3, 3]$$$, в результате чего массив станет $$$[2, 5, 6]$$$, а сумма составит $$$13$$$.

Во втором примере вам не нужно выполнять никаких операций.

В третьем примере вы можете выполнить операцию на подмассиве $$$[1, 4]$$$, в результате чего массив станет $$$[5, 5, 5, 5]$$$, а сумма составит $$$20$$$.

В четвертом примере вы можете выполнить операцию на подмассиве $$$[2, 3]$$$, в результате чего массив станет $$$[3, 5, 5, 9, 10]$$$, а сумма составит $$$32$$$.