← 返回题目列表

Codeforces · 2169/C

C. 范围操作

中文机器翻译题面 查看原题

给你一个长度为$$$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$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$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]$$$ 执行操作,得到数组 $$$[2, 5, 6]$$$ 和和 $$$13$$$。

在第二个示例中,您不需要执行任何操作。

在第三个示例中,您可以对子数组 $$$[1, 4]$$$ 执行操作,得到数组 $$$[5, 5, 5, 5]$$$ 和和 $$$20$$$。

在第四个示例中,您可以对子数组 $$$[2, 3]$$$ 执行操作,得到数组 $$$[3, 5, 5, 9, 10]$$$ 和和 $$$32$$$。