题目描述

如果一个长度为 $n$ 的数组 $a$ 满足 $a_1 \leq a_2 \leq \ldots \leq a_{n-1} \leq a_n$，则称该数组是有序的。

Ntarsis 有一个长度为 $n$ 的数组 $a$。

他可以对数组进行如下操作（可以进行零次或多次）：

• 选择一个下标 $i$（$1 \leq i \leq n-1$）。
• 将 $a_1, a_2, \ldots, a_i$ 的每个元素加 $1$。
• 将 $a_{i+1}, a_{i+2}, \ldots, a_n$ 的每个元素减 $1$。

操作后，$a$ 中的元素可以为负数。

请你求出最少需要多少次操作，才能使数组 $a$ 变为无序数组（即不满足有序条件）。

输入格式

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 500$），表示数组 $a$ 的长度。

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $500$。

输出格式

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

说明/提示

在第一个样例中，我们可以进行 $1$ 次操作使数组变为无序：

• 选择 $i = 1$。此时数组 $a$ 变为 $[2, 0]$，不再有序。

在第二个样例中，我们可以进行 $2$ 次操作使数组变为无序：

• 选择 $i = 3$。此时数组 $a$ 变为 $[2, 9, 11, 12]$。
• 再次选择 $i = 3$。此时数组 $a$ 变为 $[3, 10, 12, 11]$，不再有序。

可以证明，第一个和第二个样例中，$1$ 和 $2$ 分别是最少的操作次数。

在第三个样例中，数组本身已经无序，因此需要 $0$ 次操作。

由 ChatGPT 4.1 翻译

样例

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

1
2
0
3