Вам дан массив целых чисел $$$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$$$.
Для каждого набора входных данных выведите одно целое число — максимальная возможная сумма массива, если вы можете выполнить вышеупомянутую операцию не более одного раза.
432 5 124 441 3 2 153 2 0 9 10
1382032
В первом примере вы можете выполнить операцию на подмассиве $$$[3, 3]$$$, в результате чего массив станет $$$[2, 5, 6]$$$, а сумма составит $$$13$$$.
Во втором примере вам не нужно выполнять никаких операций.
В третьем примере вы можете выполнить операцию на подмассиве $$$[1, 4]$$$, в результате чего массив станет $$$[5, 5, 5, 5]$$$, а сумма составит $$$20$$$.
В четвертом примере вы можете выполнить операцию на подмассиве $$$[2, 3]$$$, в результате чего массив станет $$$[3, 5, 5, 9, 10]$$$, а сумма составит $$$32$$$.
