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.

给你一个长度为 $n$ 的整数数组 $a$。

你可以执行以下操作：选择一个区间 $[l, r]$（其中 $1 \le l \le r \le n$），并将元素 $a_l, a_{l+1}, \dots, a_r$ 的值全部替换为 $(l + r)$。

你的任务是：在最多执行一次上述操作的前提下，计算数组总和的最大可能值。

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

第一行包含一个整数 $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$。

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

在第一个例子中，你可以对子数组 $[3, 3]$ 执行该操作，得到数组 $[2, 5, 6]$，其元素和为 $13$。

在第二个例子中，你无需执行任何操作。

在第三个例子中，你可以对子数组 $[1, 4]$ 执行该操作，得到数组 $[5, 5, 5, 5]$，其元素和为 $20$。

在第四个例子中，你可以对子数组 $[2, 3]$ 执行该操作，得到数组 $[3, 5, 5, 9, 10]$，其元素和为 $32$。