A. Restricted Sorting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. For an integer $$$k$$$, we call it piggy if and only if it is possible to sort $$$a$$$ in non-descending order by performing the following operation an arbitrary number of times (possibly zero):

  • First, select two indices $$$i$$$ and $$$j$$$ ($$$1 \le i \lt j \le n$$$) such that $$$|a_i - a_j| \ge k$$$;
  • Then, swap $$$a_i$$$ and $$$a_j$$$.

You need to determine the largest piggy integer $$$k$$$. If such an integer does not exist, output $$$-1$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case, output a single integer — the largest piggy integer $$$k$$$.

If such an integer does not exist, output $$$-1$$$ instead.

Example
Input
5
1
1
5
1 2 3 4 5
3
1 4 2
5
2 1 5 4 3
6
1 1 4 5 1 4
Output
-1
-1
2
2
3
Note

In the first and the second test case, no matter how large $$$k$$$ is, you can always sort $$$a$$$ in non-descending order by not performing any operations.

In the third test case, the largest piggy $$$k$$$ is $$$2$$$. We can select $$$i=2$$$ and $$$j=3$$$ in the first operation, since $$$|a_2-a_3|=|4-2|=2 \ge k$$$, and $$$a$$$ is sorted in non-descending order. It can be proven that no piggy integers larger than $$$2$$$ exist.