CF2163C.Monopati

You are given a grid $a$ of $2$ rows and $n$ columns, where every cell has value from $1$ to $2n$.

Let $f(l, r)$, where $1 \le l \le r \le 2n$, represent a binary$^{\text{∗}}$ grid $b$ of $2$ rows and $n$ columns, such that $b_{i, j} = 1$ if and only if $l \le a_{i, j} \le r$. Note that cell $(i, j)$ denotes the cell $i$ rows from the top and $j$ columns from the left.

Count the number of pairs of integers $(l, r)$ such that $1 \le l \le r \le 2n$, and in $f(l, r)$ there exists a down-right path of adjacent cells$^{\text{†}}$ with value of $1$ from cell $(1, 1)$ to $(2, n)$.

$^{\text{∗}}$A grid is considered binary if and only if every cell of it has value of $\mathtt{0}$ or $\mathtt{1}$.

$^{\text{†}}$A down-right path of adjacent cells is a sequence of cells such that each cell in the sequence shares either its top side or its left side with a side of the previous cell in the sequence.

给你一个 $2$ 行 $n$ 列的网格 $a$，其中每个单元格的值均在 $1$ 到 $2n$ 之间。

定义函数 $f(l, r)$（其中 $1 \le l \le r \le 2n$）为一个 $2$ 行 $n$ 列的二进制$^{\text{∗}}$ 网格 $b$，满足：当且仅当 $l \le a_{i, j} \le r$ 时，$b_{i, j} = 1$。注意，单元格 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的单元格。

请计算满足 $1 \le l \le r \le 2n$ 的整数对 $(l, r)$ 的个数，使得在 $f(l, r)$ 中存在一条由值为 $1$ 的相邻单元格构成的向下-向右路径$^{\text{†}}$，该路径从单元格 $(1, 1)$ 出发，终止于单元格 $(2, n)$。

$^{\text{∗}}$ 当且仅当网格中每个单元格的值均为 $\mathtt{0}$ 或 $\mathtt{1}$ 时，该网格被称为二进制网格。

$^{\text{†}}$ 向下-向右路径指一串相邻单元格组成的序列，其中序列中每个单元格均与前一个单元格共享其上边或左边。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of columns in the grid.

The second line contains exactly $n$ integers $a_{1, 1}$, $a_{1, 2}$, ..., $a_{1, n}$ ($1 \le a_{1, i} \le 2n$) — the values of the cells of the first row of the grid.

The third line contains exactly $n$ integers $a_{2, 1}$, $a_{2, 2}$, ..., $a_{2, n}$ ($1 \le a_{2, i} \le 2n$) — the values of the cells of the second row of the grid.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For every test case, output on a separate line a single integer representing the number of pairs of integers $(l, r)$ such that $1 \le l \le r \le 2n$, and in $f(l, r)$ there exists a down-right path of adjacent cells with value of $1$ from cell $(1, 1)$ to $(2, n)$.

对于每个测试用例，在单独一行中输出一个整数，表示满足 $1 \le l \le r \le 2n$ 的整数对 $(l, r)$ 的个数，使得在 $f(l, r)$ 中存在一条从单元格 $(1, 1)$ 到 $(2, n)$ 的、由值为 $1$ 的相邻单元格构成的“下-右”路径。

Consider the first example.

The grids $f(1, 1), f(1, 2)$ will look like the following:

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

There does not exist a path of $1$s from the top-left cell to the bottom-right cell, therefore the pairs $(1, 1)$ and $(1, 2)$ are not counted.

The grids $f(1, 3)$ and $f(1, 4)$ will look like the following:

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

Since there exists a valid path from $(1, 1)$ to $(2, 2)$, the pairs $(1, 3)$ and $(1, 4)$ will be counted.

The grids $f(2, 2)$, $f(4, 4)$ will be the following:

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

The grids $f(2, 3)$, $f(2, 4)$, $f(3, 3)$, $f(3, 4)$ will look like the following:

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

So the pairs $(2, 3)$, $(2, 4)$, $(3, 3)$ and $(3, 4)$ will not be counted.

The only pairs counted where pairs $(1, 3)$ and $(1, 4)$, so the answer is $2$.

考虑第一个例子。

网格 $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$。