CF2229D Me When Median Problem

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.

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 $ .

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

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.