题目描述

Kevin 有一排 $n$ 列积木塔，第 $i$ 列由 $a_i$ 个相同的单位立方体垂直堆叠而成。一开始，重力是向下的，所以每列积木都稳稳地叠在地面上，从高度 $1$ 到 $a_i$ 依次排列。

突然，Kevin 发现了一个神奇的开关——只要一按，重力就会瞬间向右！每个立方体都会拼命向右滑动，但它们不能穿过其他立方体，也不能重叠，而且每个立方体必须保持自己原来的高度（不能上下移动）。最终，所有立方体会在重力作用下重新排布，形成一种唯一确定的稳定状态。

（参考下图：左边是重力向下时的初始状态，右边是重力向右后的最终状态。）

示例图

Kevin 是个爱搞破坏的玩家。在按下那个神奇的开关之前，他最多可以执行一次操作：选择某一列 $i$ ，并从该列顶部移除一个立方体（即把 $a_i$ 减少 $1$ ）。他也可以选择什么都不做。

如果一个立方体在重力向右移动后，它所在的列编号与原来不同，我们就说这个立方体“搬家”了。

Kevin 希望最大化最终“搬家”的立方体数量。请你帮他算出，在最优操作（或不操作）下，最多有多少个立方体能够成功搬家。

输入格式

第一行包含一个整数 $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$ 。

对于每个测试用例，输出一个整数——假设 Kevin 最优地执行至多一次移除操作（也可以不操作），在重力向右移动后，能够发生移动的立方体的最大可能数量。

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

在第一个测试案例中，最好在索引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的小方块不会移动，因为它们已经位于数组的最右端。

在第三个测试案例中，我们无法移动任何一个立方体。