C. Range Operation
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You 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.

Input

The 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$$$.

Output

For each test case, print a single integer — the maximum possible total array sum if you can perform the aforementioned operation at most once.

Example
Input
4
3
2 5 1
2
4 4
4
1 3 2 1
5
3 2 0 9 10
Output
13
8
20
32
Note

In 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$$$.