CF2169C Range Operation

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.

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

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

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