Absolute Sorting
Contest: Codeforces Round 839 (Div. 3)
Difficulty rating: 1400
Tags: constructive algorithms, math

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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]$$$.

Example input:
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

Example output:
4
-1
0
42
2
-1
100000000
40741153

Editorial:
What does it actually mean for an array $$$a_1, a_2, \dots, a_n$$$ to be sorted? That means $$$a_1 \le a_2$$$ and $$$a_2 \le a_3$$$ and so on.
For each pair of adajacent elements, let's deduce which values $$$x$$$ put them in the correct order. Any value of $$$x$$$ that puts all pairs in the correct order will be the answer.
Consider any $$$a_i$$$ and $$$a_{i+1}$$$ and solve the inequality $$$|a_i - x| \le |a_{i+1} - x|$$$. If $$$a_i = a_{i+1}$$$, then any value of $$$x$$$ works. Let $$$a_i$$$ be smaller than $$$a_{i+1}$$$.
If $$$x$$$ is smaller than or equal to $$$a_i$$$, then the inequality becomes $$$a_i - x \le a_{i+1} - x \Leftrightarrow a_i \le a_{i+1}$$$. Thus, they don't change their order, and any $$$x \le a_i$$$ works.
If $$$x$$$ is greater than or equal to $$$a_{i+1}$$$, then the inequality becomes $$$x - a_i \le x - a_{i+1} \Leftrightarrow a_i \ge a_{i+1}$$$. Thus, they always change their order, and none of $$$x \ge a_i$$$ work.
If $$$x$$$ is between $$$a_i$$$ and $$$a_{i+1}$$$, then the inequality becomes $$$x - a_i \le a_{i+1} - x \Leftrightarrow 2x \le a_i + a_{i+1} \Leftrightarrow x \le \frac{a_i + a_{i+1}}{2}$$$. Thus, they only remain in the same order for any integer $$$x$$$ such that $$$a_i \le x \le \lfloor \frac{a_i + a_{i+1}}{2} \rfloor$$$.
In union, that tells us that all values of $$$x$$$ that work for such a pair are $$$x \le \lfloor \frac{a_i + a_{i+1}}{2} \rfloor$$$.
The similar analysis can be applied to $$$a_i > a_{i+1}$$$, which results in the required $$$x$$$ being $$$x \ge \lceil \frac{a_i + a_{i+1}}{2} \rceil$$$ for such pairs.
Finally, how to find out if some value of $$$x$$$ passes all conditions? Among all conditions of form $$$x \le \mathit{val_i}$$$, in order for some $$$x$$$ to work, it should be less than or equal to even the smallest of them. Similarly, among all conditions of form $$$x \ge \mathit{val_i}$$$, in order for some $$$x$$$ to work, it should be greater than or equal to even the largest of them.
Thus, take the minimum over the pairs of one type. Take the maximum over the pairs of another type. If two resulting values are contradictory, then there is no answer. Otherwise, any value inside the resulting range of $$$x$$$ works.
Overall complexity: $$$O(n)$$$ per testcase.