A16672 | Monopati

给定一个 $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{†}}$ 向下-向右的相邻路径是指这样一个单元格序列：序列中的每个单元格与前一个单元格要么共享其上边（向下移动），要么共享其左边（向右移动）。

每个测试包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。随后给出各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——网格的列数。

第二行恰好包含 $n$ 个整数 $a_{1, 1}, a_{1, 2}, \dots, a_{1, n}$（$1 \le a_{1, i} \le 2n$）——网格第一行各单元格的取值。

第三行恰好包含 $n$ 个整数 $a_{2, 1}, a_{2, 2}, \dots, a_{2, n}$（$1 \le a_{2, i} \le 2n$）——网格第二行各单元格的取值。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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