Poltu is a fresher KUETian. He recently got admitted into KUET. So, as a fresher he is very excited about his university. He got a bunch of about thirty best friends in the very first week of his class (don't laugh).
In the midterm break of first semester, Poltu decided to travel home by Sundarban Express. Sundarban Express is an inter city train which departs to Dhaka from Khulna almost every night. So, Poltu and his best friends decided to travel Dhaka by this train.
The train has a strange ticket issuing system. On each ticket, there is a number printed on it. This means you can have a seat in any bogie starting from 1 to that number.
As Poltu is very friendly, he wants to enter in a bogie in which he can take some selfies with his friends. But he doesn't want to enter the most populated bogie. So, he decided to choose the second populated bogie to enter.
You are given an array A having N elements. Here A is the Train, which consists of the population of N bogies. You are also given Q queries. In each query you will be given an index idx which is the printed number on the ticket. For each test case, you have to print the population of second maximum populated bogie of the given train from position 1 to position idx. More specifically, the second maximum value of A[1] to A[idx].
Input
First line contains T (1 ≤ T ≤ 10). The number of test cases.
For each test case, the first line contains N (1 ≤ N ≤ 105), the number of bogies.
The next line contains N values. This is the array A (1 ≤ A[i] ≤ 105).
Then a line contains Q (1 ≤ Q ≤ 105). The number of queries.
Each of the next Q lines contains one index idx (1 ≤ idx ≤ N) in one line. You have to report the second maximum value of the array A from index 1 to idx.
Output
For each test case, print Q lines. Each line should contain a value v which is the output of each of the test cases which is the second maximum value in range of array A[1 ... idx]. If the second maximum does not exist, print -1.
Sample
| Input | Output |
|---|---|
2 5 1 2 3 4 5 2 4 5 5 1 2 3 4 5 2 2 4 | 3 4 1 3 |
