D. Я, когда задача на медиану
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива целых положительных чисел $$$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{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$$$. Можно доказать, что этот вариант является оптимальным.