310568: CF1853A. Desorting
Description
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.
InputEach 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$.
OutputOutput the minimum number of operations needed to make the array not sorted.
ExampleInput4 2 1 1 4 1 8 10 13 3 1 3 2 3 1 9 14Output
1 2 0 3Note
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.
Input
题意翻译
如果一个长度为 $n$ 的序列 $a$ 满足 $ a_1 \leq a_2 \leq \ldots \leq a_{n-1} \leq a_n $,我们则称序列 $a$ 是有序的。 给你一个长度为 $n$ ($2 \le n \le 500$)的序列 $a$。 你每次可以对 $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$ 变得不有序的最小操作次数。Output
这个问题是关于一个长度为n的数组a的操作。定义数组a是有序的,如果对于所有的1≤i
输入数据格式:
输入包含多个测试用例。第一行包含测试用例的数量t(1≤t≤100)。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n(2≤n≤500)——数组a的长度。
下一行包含n个整数a_1, a_2, …, a_n(1≤a_i≤10^9)——数组a的值。
保证所有测试用例的n之和不超过500。
输出数据格式:
输出使得数组a变得无序所需的最小操作次数。
示例:
输入
```
4
2
1 1
4
1 8 10 13
3
1 3 2
3
1 9 14
```
输出
```
1
2
0
3
```
注意:
- 在第一个测试用例中,我们可以进行1次操作使得数组无序:选择i=1,数组a变为[2, 0],这是无序的。
- 在第二个测试用例中,我们可以进行2次操作使得数组无序:选择i=3,数组a变为[2, 9, 11, 12];再次选择i=3,数组a变为[3, 10, 12, 11],这是无序的。
- 在第三个测试用例中,数组已经是无序的,所以不需要操作。
- 在第四个测试用例中,需要进行3次操作才能使数组无序。题目大意: 这个问题是关于一个长度为n的数组a的操作。定义数组a是有序的,如果对于所有的1≤i