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 以最佳方式应用单个减少(或选择不应用它)。
示例
输入复制
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
输出复制
81201018
注意
在第一个测试用例中,最好对索引 $$$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$$$ 处的立方体不会移动,因为它们已经位于数组的最右端。
在第三个测试用例中,无法使任何立方体移动。