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

Вам дана сетка $$$a$$$ из $$$2$$$ строк и $$$n$$$ столбцов, где каждая ячейка имеет значение от $$$1$$$ до $$$2n$$$.

Определим $$$f(l, r)$$$, где $$$1 \le l \le r \le 2n$$$, как бинарную$$$^{\text{∗}}$$$ сетку $$$b$$$ из $$$2$$$ строк и $$$n$$$ столбцов, такую что $$$b_{i, j} = 1$$$ тогда и только тогда, когда $$$l \le a_{i, j} \le r$$$. Обратите внимание, что ячейка $$$(i, j)$$$ обозначает ячейку, находящуюся на $$$i$$$-й сверху строке и $$$j$$$-м слева столбце.

Посчитайте количество пар целых чисел $$$(l, r)$$$ таких, что $$$1 \le l \le r \le 2n$$$, и в $$$f(l, r)$$$ существует идущий только вниз и вправо путь смежных ячеек$$$^{\text{†}}$$$ от ячейки $$$(1, 1)$$$ до $$$(2, n)$$$, в котором каждая ячейка имеет значение $$$1$$$.

$$$^{\text{∗}}$$$Сетка называется бинарной, если и только если каждое значение в ней равно $$$\mathtt{0}$$$ или $$$\mathtt{1}$$$.

$$$^{\text{†}}$$$Идущий только вниз и вправо путь смежных ячеек — это последовательность ячеек, такая что каждая ячейка в последовательности делит либо свою верхнюю сторону, либо свою левую сторону, с одной из сторон предыдущей ячейки в последовательности.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_{1, 1}$$$, $$$a_{1, 2}$$$, ..., $$$a_{1, n}$$$ ($$$1 \le a_{1, i} \le 2n$$$) — значения ячеек первой строки сетки.

Третья строка содержит $$$n$$$ целых чисел $$$a_{2, 1}$$$, $$$a_{2, 2}$$$, ..., $$$a_{2, n}$$$ ($$$1 \le a_{2, i} \le 2n$$$) — значения ячеек второй строки сетки.

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

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

Для каждого набора входных данных выведите на отдельной строке одно целое число — количество пар целых чисел $$$(l, r)$$$ таких, что $$$1 \le l \le r \le 2n$$$, и в $$$f(l, r)$$$ существует идущий только вниз и вправо путь смежных ячеек со значением $$$1$$$ от ячейки $$$(1, 1)$$$ до $$$(2, n)$$$.

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

Рассмотрим первый пример.

Сетки $$$f(1, 1), f(1, 2)$$$ будут выглядеть следующим образом:

$$$$$$ \mathtt{10} $$$$$$ $$$$$$ \mathtt{01} $$$$$$

Пути из ячейки в верхнем левом углу в ячейку в нижнем правом углу по ячейкам со значением $$$1$$$ не существует, поэтому пары $$$(1, 1)$$$ и $$$(1, 2)$$$ не подходят.

Сетки $$$f(1, 3)$$$ и $$$f(1, 4)$$$ будут выглядеть следующим образом:

$$$$$$ \mathtt{11} $$$$$$ $$$$$$ \mathtt{11} $$$$$$

Поскольку существует корректный путь от $$$(1, 1)$$$ до $$$(2, 2)$$$, пары $$$(1, 3)$$$ и $$$(1, 4)$$$ входят в ответ.

Сетки $$$f(2, 2)$$$, $$$f(4, 4)$$$ будут следующими:

$$$$$$ \mathtt{00} $$$$$$ $$$$$$ \mathtt{00} $$$$$$

Сетки $$$f(2, 3)$$$, $$$f(2, 4)$$$, $$$f(3, 3)$$$, $$$f(3, 4)$$$ будут выглядеть следующим образом:

$$$$$$ \mathtt{01} $$$$$$ $$$$$$ \mathtt{10} $$$$$$

Таким образом, пары $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 3)$$$ и $$$(3, 4)$$$ не подходят.

Единственные пары, которые подходят под условие, это пары $$$(1, 3)$$$ и $$$(1, 4)$$$, поэтому ответ равен $$$2$$$.