Absolute Sorting (Codeforces 1772D)
Tags: Math, constructive algorithms

You are given an array $$$a$$$ consisting of $$$n$$$ integers. The array is sorted if $$$a_1 \le a_2 \le \dots \le a_n$$$.You want to make the array $$$a$$$ sorted by applying the following operation exactly once:  choose an integer $$$x$$$, then for every $$$i \in [1, n]$$$, replace $$$a_i$$$ by $$$|a_i - x|$$$. Find any value of $$$x$$$ that will make the array sorted, or report that there is no such value.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases.Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^8$$$).Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print any integer $$$x$$$ ($$$0 \le x \le 10^9$$$) that makes the array sorted. It can be shown that if such an integer $$$x$$$ exists, there is at least one such integer between $$$0$$$ and $$$10^9$$$.If there is no such integer, then print $$$-1$$$. If there are multiple suitable values of $$$x$$$, print any of them.

Note: In the first test case, after using $$$x = 4$$$, the array becomes $$$[1, 1, 1, 1, 1]$$$.In the third test case, after using $$$x = 0$$$, the array becomes $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$.In the fourth test case, after using $$$x = 42$$$, the array becomes $$$[32, 37, 38, 39, 40, 41]$$$.

Sample Inputs:
8
5
5 3 3 3 5
4
5 3 4 5
8
1 2 3 4 5 6 7 8
6
10 5 4 3 2 1
3
3 3 1
3
42 43 42
2
100000000 99999999
6
29613295 52036613 75100585 78027446 81409090 73215

Sample Outputs:
4
-1
0
42
2
-1
100000000
40741153

Solution (Python):
import sys
input = sys.stdin.readline

class Solver:

    def solve(self, arr):
        (low, high) = (0, 10 ** 8 + 1)
        for (i, j) in zip(arr, arr[1:]):
            if i < j:
                high = min(high, (i + j) // 2)
            elif i > j:
                low = max(low, (i + j + 1) // 2)
        print(-1 if low > high else low)
if __name__ == '__main__':
    solver = Solver()
    t = int(input())
    for i in range(t):
        n = int(input())
        arr = list(map(int, input().split()))
        solver.solve(arr)

Solution (Python):
import sys
import heapq
import math
input = sys.stdin.readline
from collections import Counter, deque, defaultdict

def sieve_of_eratosthenes(n):
    sieve = [True] * (n + 1)
    (sieve[0], sieve[1]) = (False, False)
    primes = []
    for current in range(2, int(n ** 0.5) + 1):
        if sieve[current]:
            primes.append(current)
            for multiple in range(current * current, n + 1, current):
                sieve[multiple] = False
    for current in range(int(n ** 0.5) + 1, n + 1):
        if sieve[current]:
            primes.append(current)
    return primes

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def count_divisible_by(num, limit):
    return limit // num

def sum_range(a, b):
    return b * (b + 1) // 2 - a * (a - 1) // 2

def solve():
    n = inp()
    a = inlt()
    (lo, hi) = (0, 10 ** 9)
    for i in range(n - 1):
        x = a[i]
        y = a[i + 1]
        midL = (x + y) // 2
        midR = (x + y + 1) // 2
        if x < y:
            hi = min(hi, midL)
        elif y < x:
            lo = max(lo, midR)
    if lo > hi:
        print(-1)
    else:
        print(lo)

def main():
    for _ in range(inp()):
        solve()
main()

Solution (Python):
from sys import stdin
from math import ceil, floor

def absolut(array):
    c = sorted(array)
    if c == array:
        return 0
    (ma, mi) = (10000000000, -1)
    for i in range(len(array) - 1):
        (a, b) = (array[i], array[i + 1])
        if a > b:
            m = ceil((a + b) / 2)
            if m > mi:
                mi = m
        if a < b:
            m = floor((a + b) / 2)
            if m < ma:
                ma = m
    if mi <= ma:
        return mi
    else:
        return -1

def main():
    for _ in range(int(stdin.readline().strip())):
        n = stdin.readline().strip()
        numbers = list(map(int, stdin.readline().strip().split()))
        print(absolut(numbers))
main()