CF1853A.Desorting

Call an array $a$ of length $n$ sorted if $a_1 \leq a_2 \leq \ldots \leq a_{n-1} \leq a_n$.

Ntarsis has an array $a$ of length $n$.

He is allowed to perform one type of operation on it (zero or more times):

• Choose an index $i$ ($1 \leq i \leq n-1$).
• Add $1$ to $a_1, a_2, \ldots, a_i$.
• Subtract $1$ from $a_{i+1}, a_{i+2}, \ldots, a_n$.

The values of $a$ can be negative after an operation.

Determine the minimum operations needed to make $a$ not sorted.

称一个长度为 $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$ 不再有序（即不满足非递减性质）所需的最少操作次数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 500$) — the length of the array $a$.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the values of array $a$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $500$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 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$。

Output the minimum number of operations needed to make the array not sorted.

输出使数组变为非有序所需的最少操作次数。

In the first case, we can perform $1$ operation to make the array not sorted:

• Pick $i = 1$. The array $a$ then becomes $[2, 0]$, which is not sorted.

In the second case, we can perform $2$ operations to make the array not sorted:

• Pick $i = 3$. The array $a$ then becomes $[2, 9, 11, 12]$.
• Pick $i = 3$. The array $a$ then becomes $[3, 10, 12, 11]$, which is not sorted.

It can be proven that $1$ and $2$ operations are the minimal numbers of operations in the first and second test cases, respectively.

In the third case, the array is already not sorted, so we perform $0$ operations.

在第一种情况下，我们只需执行 $1$ 次操作即可使数组变为非有序：

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

在第二种情况下，我们需执行 $2$ 次操作才能使数组变为非有序：

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

可以证明：在第一个和第二个测试用例中，所需的最少操作次数分别为 $1$ 和 $2$。

在第三种情况下，数组本身已为非有序，因此我们执行 $0$ 次操作。