题目描述

如果一个长度为 n 的序列 a，满足 a₁ ≤ a₂ ≤ ... ≤ aₙ（1 ≤ aᵢ ≤ 10⁹），我们称序列 a 是有序的。

现在给你一个长度为 n（2 ≤ n ≤ 500）的序列 a，每次可以对 a 进行如下操作（可以多次进行，也可以不进行）：

1. 选择一个下标 i（1 ≤ i ≤ n-1）
2. 将 a₁, a₂, ..., aᵢ 加 1
3. 将 aᵢ₊₁, aᵢ₊₂, ..., aₙ 减 1

执行操作后，aᵢ 可以为负数。
请计算：最少需要进行几次操作可以使数组 a 变为无序（即不满足非降序关系）。

输入格式

每个测试包含多个测试用例。
第一行包含测试用例的数量 t（1 ≤ t ≤ 100）。

下面是每个测试用例的描述：
每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 500），表示数组的长度。
下一行包含 n 个整数 a₁, a₂, ..., aₙ（1 ≤ aᵢ ≤ 10⁹），表示数组的初始状态。

输出格式

输出使数组无序所需的最小操作次数。

每个测试用例输出一行，表示最小操作次数。

输入样例 #1

4  
2  
1 1  
4  
1 8 10 13  
3  
1 3 2  
3  
1 9 14

输出样例 #1

1  
2  
0  
3