E. Swap Task
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In Sultan Malik's palace, there are $$$N$$$ antiques, each with a distinct value. Initially, the antiques are arranged randomly in the entrance of his palace.

Sultan Malik, known for his love of perfection, wishes to sort his antiques in ascending order of their values.

The Sultan is looking for a wise advisor, so he makes this task into a game. You can only sort the antiques using swaps. Moreover, there is another restriction: a swap is only allowed if one antique has a value strictly greater than a chosen threshold $$$K$$$, and the other has a value strictly lower than $$$K$$$.

Formally, given an array $$$A$$$ of $$$N$$$ distinct integers, you want to sort it with the following operation:

  • $$$swap(A_i, A_j)$$$ only if $$$A_i \gt K$$$ and $$$A_j \lt K$$$, where $$$K \ge 0$$$.

The Sultan will select the advisor who can find the smallest possible $$$K$$$ that allows the antiques to be sorted in increasing order.

Fankoush, aspiring to be the Sultan's advisor, asked for your help to determine $$$K$$$.

If there exists no such $$$K$$$, you must report $$$-1$$$ to Fankoush.

Input

The first line contains an integer $$$T$$$ denoting the number of test cases ($$$ 1 \le T \le 10^5 $$$). For each test case:

  • The first line contains an integer $$$N$$$, the size of the array ($$$ 2 \le N \le 10^5 $$$).
  • The second line contains $$$N$$$ distinct integers, the $$$i^{th}$$$ integer representing the array $$$A_i$$$ ($$$ 1 \le A_i \le 10^9 $$$).
It is guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$4.10^5$$$.
Output

Print the minimum possible $$$K$$$ or $$$-1$$$ if it is not possible.

Example
Input
4
2
3 1
2
2 1
3
1 2 3
5
2 4 3 1 5
Output
2
-1
0
3