Yousef 有 $$$n$$$ 并排站立的立方体列。第 $$$i$$$ 列包含垂直堆叠的 $$$a_i$$$ 相同单位立方体。最初,重力将立方体向下拉,因此每列 $$$i$$$ 恰好包含高度为 $$$1, 2, \dots, a_i$$$ 的 $$$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 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——Yousef 可以达到的最大可能总移动距离(所有剩余立方体的移动距离之和)。
示例
输入复制
551 2 3 2 175 4 1 1 1 1 361 2 3 4 5 664 1 6 3 2 671 3 2 7 2 3 1
输出复制
93701729
注意
在第一个测试用例中,初始总移动距离为$$$5$$$。如果 Yousef 删除索引 $$$5$$$ 处的多维数据集,则数组将变为 $$$[1, 2, 3, 2, 0]$$$。因为第五列现在是空的,所以前四列中的所有立方体都能够比原来更向右滑动。这导致新的总距离为 $$$9$$$。
在第三个测试用例中,初始总移动距离为$$$0$$$。即使尤瑟夫移除任何立方体,剩余的立方体也将无法移动。这导致总距离为 $$$0$$$。