← 返回题目列表

Codeforces · 2227/E

E. 一切都变了

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

Yousef 有 $$$n$$$ 并排站立的立方体列。第 $$$i$$$ 列包含垂直堆叠的 $$$a_i$$$ 相同单位立方体。最初,重力将立方体向下拉,因此每列 $$$i$$$ 恰好包含高度为 $$$1, 2, \dots, a_i$$$ 的 $$$a_i$$$ 立方体。

突然,重力向右移动。每个立方体尽可能向右水平滑动。立方体不能穿过或重叠其他立方体,并且必须保持其原始高度。最终的配置由初始高度唯一确定。

施加向右重力之前和之后。

在重心转移之前,优素福可能会执行 最多 1 个 操作:选择一个索引$$$i$$$并将$$$a_i$$$减少$$$1$$$(即从该列中删除一个立方体)。他也可能选择什么都不做。

据说立方体 移动 如果重心偏移后的列索引与其原始列索引不同。

假设 Yousef 以最佳方式应用单次减少(或选择不应用),求重力转移后可能移动的最大立方体数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 重力转移后可能移动的立方体的最大数量,假设 Yousef 以最佳方式应用单个减少(或选择不应用它)。

示例

输入
复制

5
5
1 2 3 2 1
7
5 4 1 1 1 1 3
6
1 2 3 4 5 6
6
4 1 6 3 2 6
7
1 3 2 7 2 3 1

输出
复制

8
12
0
10
18

注意

在第一个测试用例中,最好对索引 $$$5$$$ 执行操作,使数组 $$$a = [1, 2, 3, 2, 0]$$$。重力转移后,所有剩余的立方体都会移动。答案是$$$1+2+3+2 = 8$$$。可以证明,更大的答案并不存在。

在第二个测试用例中,我们可以对索引$$$6$$$执行操作,使得数组$$$a = [5, 4, 1, 1, 1, 0, 3]$$$。重力转移后,$$$5+4+1+1+1 = 12$$$ 立方体将移动。请注意,索引 $$$7$$$ 处的立方体不会移动,因为它们已经位于数组的最右端。

在第三个测试用例中,无法使任何立方体移动。