← 返回题目列表

Codeforces · 2229/D

D. 我当中值问题

中文机器翻译题面 查看原题

给定两个正整数数组 $$$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)$$$ 可达到的最大值。

示例

输入
复制

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

输出
复制

1
3
6
8
14
8

注意

在第一个示例中,我们不需要执行任何操作,因此答案只是 $$$\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}]$$$
则答案为$$$\min(3, 5)$$$ 即$$$3$$$,可以证明这是最优的。