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.

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.

Restricted Sorting

Examples