题目描述

给定一个长度为 $n$ 的整数数组 $a$。 可以执行以下一次操作（也可以不执行任何操作）：

• 选择一个区间 $[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$）。

额外约束：所有测试用例中 $\sum n \le 2\cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数——在最多执行一次操作的情况下，数组总和的最大可能值。

样例输入

4
3
2 5 1
2
4 4
4
1 3 2 1
5
3 2 0 9 10

样例输出

13
8
20
32

说明

样例解释

• 第一个样例：对区间 $[3,3]$ 进行替换，$l+r=6$，数组变为 $[2,5,6]$，和为 $13$。
• 第二个样例：不进行操作时已为最优，总和为 $8$。
• 第三个样例：对区间 $[1,4]$ 进行替换，$l+r=5$，数组变为 $[5,5,5,5]$，和为 $20$。
• 第四个样例：对区间 $[2,3]$ 进行替换，$l+r=5$，数组变为 $[3,5,5,9,10]$，和为 $32$。