题目描述

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

突然，重力方向转向右侧。每个立方体会在保持原有高度的前提下，朝右侧水平滑动至能到达的最右位置。立方体不能越过或重叠其它立方体。最终立方体的分布由初始高度唯一确定。

在重力改变之前，Yousef 可以至多进行一次操作：选择一个下标 $i$，将 $a_i$ 减小 $1$（即从该列移除一个立方体）。他也可以选择不进行任何操作。

一个立方体的移动距离定义为 $|j-i|$，其中 $i$ 是它初始所在的列，$j$ 是重力变化后它停留的列。

请你计算，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 \times 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

9
37
0
17
29

样例说明

在第一个测试用例中，初始总移动距离是 $5$。如果 Yousef 移除第 $5$ 列的立方体，数组变成 $[1, 2, 3, 2, 0]$。因为第五列现在为空，前四列的所有立方体都能比之前滑得更远，最终总移动距离变为 $9$。

在第三个测试用例中，初始总移动距离为 $0$。即便 Yousef 移除任意立方体，也不会影响剩余立方体的可移动距离，因此总距离仍为 $0$。

由 ChatGPT 5 翻译

来源

Codeforces 2227F，英文题名 It Just Keeps Going Sideways。