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

Вы играете в новую карточную игру в казино со следующими правилами:

  1. В игре используется колода из $$$2n$$$ карт с различными номиналами.
  2. Колода делится поровну между игроком и дилером: каждый получает по $$$n$$$ карт.
  3. В течение $$$n$$$ раундов игрок и дилер одновременно выкладывают по одной верхней карте из своей руки. Карты сравниваются, и очко получает тот, чья карта имеет больший номинал. Победившая карта убирается из игры, а проигравшая возвращается обратно в руку и кладётся поверх остальных карт в руку того, кто её выложил.

Обратите внимание, что игра всегда длится ровно $$$n$$$ раундов.

Вы проследили за тасовкой карт и знаете порядок карт в руке дилера (сверху вниз). Вы хотите максимизировать своё количество очков, поэтому можете поменять местами в своей руке любые две карты не более чем один раз (чтобы не вызывать подозрений).

Определите максимальное количество очков, которое вы можете получить.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^{5}$$$) — количество карт в руке игрока.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \leq a_{i} \leq 2n$$$) — номиналы карт в руке игрока сверху вниз.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_{1}, b_{2}, \ldots, b_{n}$$$ ($$$1 \leq b_{i} \leq 2n$$$) — номиналы карт в руке дилера сверху вниз.

Гарантируется, что номиналы всех карт различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество очков, которое вы можете получить.

Пример
Входные данные
3
7
13 7 4 9 12 10 2
6 1 14 3 8 5 11
3
1 6 5
2 3 4
5
8 6 3 10 1
7 9 5 2 4
Выходные данные
6
2
3
Примечание

В первом наборе входных данных можно не менять карты. Игровой процесс будет устроен следующим образом:

  1. Сравниваются карты с номиналами $$$13$$$ и $$$6$$$. Побеждает игрок и получает очко.
  2. Сравниваются карты с номиналами $$$7$$$ и $$$6$$$. Побеждает игрок и получает очко.
  3. Сравниваются карты с номиналами $$$4$$$ и $$$6$$$. Побеждает дилер.
  4. Сравниваются карты с номиналами $$$4$$$ и $$$1$$$. Побеждает игрок и получает очко.
  5. Сравниваются карты с номиналами $$$9$$$ и $$$1$$$. Побеждает игрок и получает очко.
  6. Сравниваются карты с номиналами $$$12$$$ и $$$1$$$. Побеждает игрок и получает очко.
  7. Сравниваются карты с номиналами $$$10$$$ и $$$1$$$. Побеждает игрок и получает очко.
Таким образом, игрок получил $$$6$$$ очков.

Во втором наборе входных данных можно поменять карты с номиналами $$$1$$$ и $$$5$$$, тогда рука игрока выглядит следующим образом $$$[5, 6, 1]$$$. Игровой процесс будет устроен следующим образом:

  1. Сравниваются карты с номиналами $$$5$$$ и $$$2$$$. Побеждает игрок и получает очко.
  2. Сравниваются карты с номиналами $$$6$$$ и $$$2$$$. Побеждает игрок и получает очко.
  3. Сравниваются карты с номиналами $$$1$$$ и $$$2$$$. Побеждает дилер.
Таким образом, игрок получил $$$2$$$ очка.

В третьем наборе входных данных можно поменять карты с номиналами $$$3$$$ и $$$10$$$, тогда рука игрока выглядит следующим образом $$$[8, 6, 10, 3, 1]$$$. Игровой процесс будет устроен следующим образом:

  1. Сравниваются карты с номиналами $$$8$$$ и $$$7$$$. Побеждает игрок и получает очко.
  2. Сравниваются карты с номиналами $$$6$$$ и $$$7$$$. Побеждает дилер.
  3. Сравниваются карты с номиналами $$$6$$$ и $$$9$$$. Побеждает дилер.
  4. Сравниваются карты с номиналами $$$6$$$ и $$$5$$$. Побеждает игрок и получает очко.
  5. Сравниваются карты с номиналами $$$10$$$ и $$$5$$$. Побеждает игрок и получает очко.
Таким образом, игрок получил $$$3$$$ очка.