Absolute Sorting

题意翻译

给定一个长度为 $n$ 的正整数序列 $a$，选择一个整数 $x$，将所有的 $a_i$ 变为 $|x-a_i|$，求能满足 $a_1\le a_2\le...\le a_n$ 和 $0\le x\le 10^9$ 的一个解 $x$。如果存在这样的一个 $x$ 请直接输出，如果无解请输出 $-1$. 数据范围：$1\le a_i\le10^8，2\le n\le2\cdot 10^5,1\le t\le2\cdot 10^4$。

题目描述

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.

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

4
-1
0
42
2
-1
100000000
40741153

说明

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

**绝对排序**

**题意翻译**
给定一个长度为 $ n $ 的正整数序列 $ a $，选择一个整数 $ x $，将所有的 $ a_i $ 变为 $ |x-a_i| $，求能满足 $ a_1 \le a_2 \le \dots \le a_n $ 和 $ 0 \le x \le 10^9 $ 的一个解 $ x $。如果存在这样的一个 $ x $ 请直接输出，如果无解请输出 $ -1 $。

数据范围：$ 1 \le a_i \le 10^8，2 \le n \le 2 \cdot 10^5, 1 \le t \le 2 \cdot 10^4 $。

**题目描述**
你有一个包含 $ n $ 个整数的数组 $ a $。如果 $ a_1 \le a_2 \le \dots \le a_n $，则该数组是有序的。

你想要通过执行以下操作恰好一次来使数组 $ a $ 有序：

- 选择一个整数 $ x $，然后对于每个 $ i \in [1, n] $，用 $ |a_i - x| $ 替换 $ a_i $。

找到任何使数组有序的 $ x $ 的值，或者报告没有这样的值。

**输入输出格式**

**输入格式**
第一行包含一个整数 $ t $ ( $ 1 \le t \le 2 \cdot 10^4 $ ) — 测试用例的数量。

每个测试用例包含两行。第一行包含一个整数 $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ )。第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^8 $ )。

输入的附加限制：所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。

**输出格式**
对于每个测试用例，打印一个整数 $ x $ ( $ 0 \le x \le 10^9 $ )，该整数使数组有序。可以证明，如果存在这样的整数 $ x $，至少有一个这样的整数在 $ 0 $ 和 $ 10^9 $ 之间。

如果没有这样的整数，则打印 $ -1 $。如果有多个合适的 $ x $ 值，打印其中任何一个。

**输入输出样例**

**输入样例 #1**
```
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
```

**输出样例 #1**
```
4
-1
0
42
2
-1
100000000
40741153
```

**说明**
在第一个测试案例中，使用 $ x = 4 $ 后，数组变为 $ [1, 1, 1, 1, 1] $。

在第三个测试案例中，使用 $ x = 0 $ 后，数组变为 $ [1, 2, 3, 4, 5, 6, 7, 8] $。

在第四个测试案例中，使用 $ x = 42 $ 后，数组变为 $ [32, 37, 38, 39, 40, 41] $。**绝对排序** **题意翻译** 给定一个长度为 $ n $ 的正整数序列 $ a $，选择一个整数 $ x $，将所有的 $ a_i $ 变为 $ |x-a_i| $，求能满足 $ a_1 \le a_2 \le \dots \le a_n $ 和 $ 0 \le x \le 10^9 $ 的一个解 $ x $。如果存在这样的一个 $ x $ 请直接输出，如果无解请输出 $ -1 $。 数据范围：$ 1 \le a_i \le 10^8，2 \le n \le 2 \cdot 10^5, 1 \le t \le 2 \cdot 10^4 $。 **题目描述** 你有一个包含 $ n $ 个整数的数组 $ a $。如果 $ a_1 \le a_2 \le \dots \le a_n $，则该数组是有序的。 你想要通过执行以下操作恰好一次来使数组 $ a $ 有序： - 选择一个整数 $ x $，然后对于每个 $ i \in [1, n] $，用 $ |a_i - x| $ 替换 $ a_i $。 找到任何使数组有序的 $ x $ 的值，或者报告没有这样的值。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $ ( $ 1 \le t \le 2 \cdot 10^4 $ ) — 测试用例的数量。 每个测试用例包含两行。第一行包含一个整数 $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ )。第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^8 $ )。 输入的附加限制：所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试用例，打印一个整数 $ x $ ( $ 0 \le x \le 10^9 $ )，该整数使数组有序。可以证明，如果存在这样的整数 $ x $，至少有一个这样的整数在 $ 0 $ 和 $ 10^9 $ 之间。 如果没有这样的整数，则打印 $ -1 $。如果有多个合适的 $ x $ 值，打印其中任何一个。 **输入输出样例** **输入样例 #1** ``` 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 ``` **输出样例 #1** ``` 4 -1 0 42 2 -1 100000000 40741153 ``` **说明** 在第一个测试案例中，使用 $ x = 4 $ 后，数组变为 $ [1, 1, 1, 1, 1] $。 在第三个测试案例中，使用 $ x = 0 $ 后，数组变为 $ [1, 2, 3, 4, 5, 6, 7, 8] $。 在第四个测试案例中，使用 $ x = 42 $ 后，数组变为 $ [32, 37, 38, 39, 40, 41] $。