time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Call an array a𝑎 of length n𝑛 sorted if a1≤a2≤…≤an−1≤an𝑎1≤𝑎2≤…≤𝑎𝑛−1≤𝑎𝑛.

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≤i≤n−11≤𝑖≤𝑛−1).
• Add 11 to a1,a2,…,ai𝑎1,𝑎2,…,𝑎𝑖.
• Subtract 11 from ai+1,ai+2,…,an𝑎𝑖+1,𝑎𝑖+2,…,𝑎𝑛.

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

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

Input

Each test contains multiple test cases. The first line contains the number of test cases t𝑡 (1≤t≤1001≤𝑡≤100). The description of the test cases follows.

The first line of each test case contains a single integer n𝑛 (2≤n≤5002≤𝑛≤500) — the length of the array a𝑎.

The next line contains n𝑛 integers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (1≤ai≤1091≤𝑎𝑖≤109) — the values of array a𝑎.

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

Output

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

Example

input

Copy

4

2

1 1

4

1 8 10 13

3

1 3 2

3

1 9 14

output

Copy

1
2
0
3

Note

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

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

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

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

It can be proven that 11 and 22 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 00 operations.

解题说明：此题是让数列不要递增，然后找到最少的次数，比较容易想到找出数列中前后差值最小的情况，然后改变这前后一对数即可。

#include<stdio.h>
int main()
{int n;scanf("%d", &n);while (n--) {int m, a[500], min = 1000000000;scanf("%d", &m);scanf("%d", &a[0]);for (int i = 1; i < m; i++){scanf("%d", &a[i]);min = (min < a[i] - a[i - 1]) ? min :( a[i] - a[i - 1]);}if (min < 0){printf("0");}else if (min == 0){printf("1");}else{printf("%d", min / 2 + 1);}printf("\n");}return 0;
}