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.

给你两个长度均为 $n$ 的正整数数组 $a$ 和 $b$。你将恰好执行以下操作 $n - 1$ 次：

• 设 $m$ 为当前 $a$ 和 $b$ 的长度（注意：两数组长度始终相等）；
• 选择一个整数 $i$（满足 $1 \le i < m$）：
  • 令 $S$ 为多重集 $\{a_i, a_{i + 1}, b_i, b_{i + 1}\}$；
  • 将 $S$ 中的元素升序排序，得到 $s_1 \le s_2 \le s_3 \le s_4$；
  • 现在将 $a_i, a_{i + 1}$ 替换为 $s_2$，并将 $b_i, b_{i + 1}$ 替换为 $s_3$。更准确地说，将 $a$ 替换为 $[a_1,a_2,\ldots,a_{i - 1},s_2,a_{i + 2},\ldots,a_m]$，将 $b$ 替换为 $[b_1,b_2,\ldots,b_{i - 1},s_3,b_{i + 2},\ldots,b_m]$。

执行完所有操作后，$a$ 和 $b$ 中均恰好剩余 $1$ 个元素。若你可以最优地执行所有操作，求最终 $\min(a_1, b_1)$ 的最大可能值。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 表示数组 $a$ 和 $b$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_{n}$（$1 \le a_i \le 2 \cdot n$）。

每个测试用例的第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_{n}$（$1 \le b_i \le 2 \cdot n$）。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

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

对于每个测试用例，输出可达到的 $\min(a_1,b_1)$ 的最大值。

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.

在第一个例子中，我们无需执行任何操作，因此答案即为 $\min(1, 2)$，也就是 $1$。

对于第二个例子，我们可以执行以下操作序列：

• 选择 $i = 1$，然后：
  • $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]$
• 再次选择 $i = 1$，然后：
  • $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}]$

此时答案为 $\min(3, 5)$，即 $3$；可以证明该结果是最优的。