Desorting (Codeforces 1853A)
Tags: Math, brute force

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.

Input: 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$$$.

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

Note: 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.

Sample Inputs:
4
2
1 1
4
1 8 10 13
3
1 3 2
3
1 9 14

Sample Outputs:
1
2
0
3

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    m = 10 ** 9
    for i in range(n - 1):
        if a[i] > a[i + 1]:
            m = -1
            break
        m = min(m, a[i + 1] - a[i])
    print(m // 2 + 1)

Solution (Python):
T = int(input())
for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    minDiff = float('inf')
    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            print(0)
            break
        else:
            minDiff = min(minDiff, arr[i + 1] - arr[i])
    else:
        print(minDiff // 2 + 1)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    d = list(map(int, input().split()))
    diff = []
    f = False
    for i in range(len(d) - 1):
        if d[i + 1] >= d[i]:
            diff.append(d[i + 1] - d[i])
        else:
            f = True
            break
    if f:
        print(0)
    else:
        mingap = min(diff)
        print(mingap // 2 + 1)