A16740 | $Range Operation$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

对于每个测试用例，输出一个整数，表示在至多进行一次操作后数组的最大和。

输入 #1

输出 #1

C++ 编辑器

输入

输出