Sequence

Time Limit: 5000 ms Memory Limit: 65536 KiB

Problem Description

We define an element $a_i$ in a sequence "good", if and only if there exists a $j(1\le j < i)$ such that $a_j < a_i$.
Given a permutation $p$ of integers from $1$ to $n$. Remove an element from the permutation such that the number of "good" elements is maximized.

Input

The input consists of several test cases. The first line of the input gives the number of test cases, $T(1\le T\le 10^3)$.
For each test case, the first line contains an integer $n(1\le n\le 10^6)$, representing the length of the given permutation.
The second line contains $n$ integers $p_1,p_2,\cdots,p_n(1\le p_i\le n)$, representing  the given permutation $p$.
It’s guaranteed that $\sum n\le 2\times 10^7$.

Output

For each test case, output one integer in a single line, representing the element that should be deleted. If there are several answers, output the minimal one.
 

Sample Input

2
1
1
5
5 1 2 3 4

Sample Output

1
5

Hint

由于本 OJ 评测机不如现场赛评测机优秀,故时限放宽。

Source

“浪潮杯”山东省第九届ACM大学生程序设计竞赛(感谢山东财经大学)