给定两个正整数数组 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$。您将执行以下操作 $$$n - 1$$$ 次:
- 设 $$$m$$$ 为 $$$a$$$ 和 $$$b$$$ 的当前长度,请注意,长度始终相等。
- 选择一个整数 $$$i$$$ ($$$1 \le i \lt 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)$$$ 的最大值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出 $$$\min(a_1,b_1)$$$ 可达到的最大值。
示例
输入复制
611232 4 51 3 647 5 4 84 6 7 888 7 13 11 1 10 4 511 11 12 8 9 2 3 13916 1 9 12 5 18 10 10 1614 6 7 11 12 17 18 3 1763 6 12 4 10 122 3 2 7 8 9
输出复制
1368148
注意
在第一个示例中,我们不需要执行任何操作,因此答案只是 $$$\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{红色}{2, 4}, 5] \rightarrow [\color{红色}{2}, 5]$$$
- $$$b = [\color{红色}{1, 3}, 6] \rightarrow [\color{红色}{3}, 6]$$$
- 选择 $$$i = 1$$$ 然后
- $$$S = \{2, 5, 3, 6\}$$$, $$$s_1 = 2$$$, $$$s_2 = 3$$$, $$$s_3 = 5$$$, $$$s_4 = 6$$$
- $$$a = [\color{红色}{2, 5}] \rightarrow [\color{红色}{3}]$$$
- $$$b = [\color{红色}{3, 6}] \rightarrow [\color{红色}{5}]$$$