CF1853A Desorting

如果一个长度为 $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 翻译