D. 好日程安排 / Good Schedule

题目描述

Alice 和 Bob 决定看一部共 $n$ 集的电视剧，编号 $1$ 到 $n$。该剧将在接下来的 $n$ 天播出。不幸的是，他们住在不同城市，播放安排不同。在第 $i$ 天，Alice 所在城市播出第 $a_i$ 集，Bob 所在城市播出第 $b_i$ 集。

他们计划选择一个连续的天数区间 $[L, R]$ ($1 \le L \le R \le n$) 来看剧。初始时两人都没看过任何集。对于区间内的每一天 $i$：

• 如果 Alice 已经看过第 $1, 2, \dots, a_i-1$ 集但还没看过第 $a_i$ 集，则她在这天看第 $a_i$ 集；否则她这天什么都不看；
• 如果 Bob 已经看过第 $1, 2, \dots, b_i-1$ 集但还没看过第 $b_i$ 集，则他在这天看第 $b_i$ 集；否则他这天什么都不看。

为了防止剧透，Alice 和 Bob 希望选择区间 $[L, R]$ 使得在区间内的每一天满足：

• 要么两人在这天看的是同一集；
• 要么两人这天都没看。

求满足条件的区间 $[L, R]$ 的数量。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例数量。

每个测试用例包含三行：

• 第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)；
• 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$)。

额外限制：所有测试用例中 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 — 满足条件的区间 $[L, R]$ 数量。

样例

3
3
1 2 1
1 2 1
2
2 1
2 2
4
1 2 3 1
1 2 3 4

6
1
6

提示

第一个例子中，合法区间为 $[1, 1]$、$[1, 2]$、$[1, 3]$ 和 $[2, 2]$。