L. Guess What: Another Permutation Game
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a permutation$$$^{[3]}$$$ $$$p$$$ of length $$$n$$$ and two integers $$$k_1$$$ and $$$k_2$$$, both not exceeding $$$n$$$. There is also an integer array $$$a$$$, initially empty. Obada and Osama are playing a game. Obada starts first, and the players alternate turns. On their turn, the player must do one of the following:

  • Remove the leftmost element from $$$p$$$ and append it to the end of the array $$$a$$$.
  • Append $$$0$$$ to the end of the array $$$a$$$.

There is one restriction, the player can't make a move that makes the array $$$a$$$ invalid.

The array $$$a$$$ is invalid when at least one of the following two conditions hold:

  • The array $$$a$$$ contains a subarray of length more than $$$k_1$$$ that contains no $$$0s$$$.
  • The array $$$a$$$ contains a subarray of length more than $$$k_2$$$ which elements are all $$$0s$$$.

The game ends when $$$p$$$ is empty, and the score of the game is equal to the largest number removed from the permutation by Obada in his turn.

Obada wants to maximize the score of the game, while Osama wants to minimize it. You are asked to find the score of the game if both players play optimally.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — representing the number of test cases.

The first line of each test case contains three space separated integers $$$n$$$, $$$k_1$$$ and $$$k_2$$$ ($$$1 \le n \le 10^6, 1 \le k_1, k_2 \le n$$$).

The second line of each test case contains $$$n$$$ space separated integers $$$p_1, p_2, ..., p_n$$$ ($$$1 \le p_i \le n$$$) — representing the permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, print a single line containing the final score of the game.

Example
Input
3
3 1 1
2 3 1
3 2 1
2 3 1
1 1 1
1
Output
3
3
1