C. Range Operationtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given an integer array $$$a$$$ of length $$$n$$$. You can perform the following operation: choose a range $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) and replace the value of elements $$$a_l, a_{l+1}, \dots, a_r$$$ with $$$(l + r)$$$.Your task is to calculate the maximum possible total array sum if you can perform the aforementioned operation at most once.InputThe first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2n$$$).Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.OutputFor each test case, print a single integer — the maximum possible total array sum if you can perform the aforementioned operation at most once.ExampleInput432 5 124 441 3 2 153 2 0 9 10Output1382032NoteIn the first example, you can perform the operation on the subarray $$$[3, 3]$$$, resulting in the array $$$[2, 5, 6]$$$ and the sum $$$13$$$.In the second example, you don't need to perform any operation.In the third example, you can perform the operation on the subarray $$$[1, 4]$$$, resulting in the array $$$[5, 5, 5, 5]$$$ and the sum $$$20$$$.In the fourth example, you can perform the operation on the subarray $$$[2, 3]$$$, resulting in the array $$$[3, 5, 5, 9, 10]$$$ and the sum $$$32$$$.