为您提供一个由 $$$2$$$ 行和 $$$n$$$ 列组成的网格 $$$a$$$,其中每个单元格的值从 $$$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, 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}$$$, ..., $$$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)$$$ 到 $$$f(l, r)$$$ 的相邻单元格的右下路径,其值为 $$$1$$$ 到$$$(2,n)$$$。
示例
输入复制
521 33 131 2 33 2 141 5 5 55 3 1 248 8 8 88 8 8 866 6 5 7 9 121 4 2 8 5 6
输出复制
254825
注意
考虑第一个例子。
网格 $$$f(1, 1), f(1, 2)$$$ 将如下所示:
$$\mathtt{10}$$ $$\mathtt{01}$$
不存在从左上角单元格到右下角单元格的 $$$1$$$s 路径,因此 $$$(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$$$。