题目描述

给定两个长度均为 $n$ 的正整数数组 $a$ 和 $b$。

你需要恰好进行 $n-1$ 次操作。一次操作如下：

• 设当前两个数组长度为 $m$，二者长度始终相等；
• 选择一个整数 $i$（$1 \le i < m$）；
• 令多重集 $S=\{a_i,a_{i+1},b_i,b_{i+1}\}$，将其中元素排序为 $s_1 \le s_2 \le s_3 \le s_4$；
• 用 $s_2$ 替换 $a_i,a_{i+1}$，用 $s_3$ 替换 $b_i,b_{i+1}$。也就是说，数组长度减少 $1$。

所有操作结束后，$a$ 和 $b$ 中都只剩下一个元素。请最大化最终的 $\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 2n$）。

第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$（$1 \le b_i \le 2n$）。

保证所有测试数据的 $n$ 之和不超过 $10^5$。

输出格式

对于每组测试数据，输出最终可以达到的 $\min(a_1,b_1)$ 的最大值。

样例 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

约束与提示

• 时间限制：2 秒

• 内存限制：256 MB

• 原题编号：CF2229D