D. Me When Median Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays of positive integers $$$a$$$ and $$$b$$$, both of length $$$n$$$. You will perform the following operation exactly $$$n - 1$$$ times:

  • let $$$m$$$ be the current length of $$$a$$$ and $$$b$$$, note that the lengths will always be equal.
  • select an integer $$$i$$$ ($$$1 \le i \lt m$$$):
    • let $$$S$$$ be the multiset $$$\{a_i, a_{i + 1}, b_i, b_{i + 1}\}$$$
    • sort the elements of $$$S$$$ such that $$$s_1 \le s_2 \le s_3 \le s_4$$$.
    • now replace $$$a_i, a_{i + 1}$$$ with $$$s_2$$$ and $$$b_i, b_{i + 1}$$$ with $$$s_3$$$. More formally, replace $$$a$$$ with $$$[a_1,a_2,\ldots,a_{i - 1},s_2,a_{i + 2},\ldots,a_m]$$$, and replace $$$b$$$ with $$$[b_1,b_2,\ldots,b_{i - 1},s_3,b_{i + 2},\ldots,b_m]$$$.

After performing all operations, there will be exactly $$$1$$$ element remaining in both $$$a$$$ and $$$b$$$. Determine the maximum value of $$$\min(a_1, b_1)$$$ attainable if you perform operations optimally.

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 testcase contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the arrays $$$a$$$ and $$$b$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_{n}$$$ ($$$1 \le a_i \le 2 \cdot n$$$).

The third line of each testcase contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_{n}$$$ ($$$1 \le b_i \le 2 \cdot n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each testcase, output the maximum value of $$$\min(a_1,b_1)$$$ attainable.

Example
Input
6
1
1
2
3
2 4 5
1 3 6
4
7 5 4 8
4 6 7 8
8
8 7 13 11 1 10 4 5
11 11 12 8 9 2 3 13
9
16 1 9 12 5 18 10 10 16
14 6 7 11 12 17 18 3 17
6
3 6 12 4 10 12
2 3 2 7 8 9
Output
1
3
6
8
14
8
Note

In the first example, we do not need to perform any operations, so the answer is just $$$\min(1, 2)$$$ which is $$$1$$$.

For the second example, we can do the following sequence of moves:

  • select $$$i = 1$$$ and then:
    • $$$S = \{2, 4, 1, 3\}$$$, $$$s_1 = 1$$$, $$$s_2 = 2$$$, $$$s_3 = 3$$$, $$$s_4 = 4$$$
    • $$$a = [\color{red}{2, 4}, 5] \rightarrow [\color{red}{2}, 5]$$$
    • $$$b = [\color{red}{1, 3}, 6] \rightarrow [\color{red}{3}, 6]$$$
  • select $$$i = 1$$$ and then
    • $$$S = \{2, 5, 3, 6\}$$$, $$$s_1 = 2$$$, $$$s_2 = 3$$$, $$$s_3 = 5$$$, $$$s_4 = 6$$$
    • $$$a = [\color{red}{2, 5}] \rightarrow [\color{red}{3}]$$$
    • $$$b = [\color{red}{3, 6}] \rightarrow [\color{red}{5}]$$$
The answer is then $$$\min(3, 5)$$$ which is $$$3$$$, it can be proven that this is optimal.