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.