题目描述

Yousef 有 $n$ 列方块并排竖立。第 $i$ 列包含 $a_i$ 个完全相同的单元方块垂直堆叠而成。最初，重力向下作用，因此每一列 $i$ 恰好包含 $a_i$ 个方块，这些方块分别处于高度 $1, 2, \dots, a_i$。

突然间，重力转向右侧。每个方块会在保持原有高度不变的前提下，尽可能水平向右滑动。方块不能穿过或重叠在其它方块上。最终配置将唯一由初始高度决定。

在重力转向之前，Yousef 可以进行至多一次操作：选择一个下标 $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$ 列的方块不会移动，因为它们本就在最右侧。

在第三个测试用例中，无论如何操作，都没有方块会移动。

由 ChatGPT 5 翻译

来源

Codeforces 2227E，英文题名 It All Went Sideways。