#P18022. Prefix MEX Equation

Prefix MEX Equation

Prefix MEX Equation

对于长度相同的两个数组 X,YX,Y,你可以执行任意次操作:选择一个下标 ii,交换 XiX_i 和 YiY_i。

一个整数集合的 MEX 是其中没有出现的最小非负整数。数组 ZZ 的前缀 MEX 数组 PP 定义为

Pi=MEX⁡(Z1,Z2,…,Zi).P_i=\operatorname{MEX}(Z_1,Z_2,\ldots,Z_i).

如果存在一组上述交换操作,使得 XX 和 YY 的前缀 MEX 数组完全相同,则称 (X,Y)(X,Y) 是一对好数组。也就是说,需要同一组交换使所有前缀同时满足要求。

给定两个长度为 NN 的数组 A,BA,B,求有多少对下标 (L,R)(L,R) 满足 1≤L≤R≤N1\le L\le R\le N,并且

$$(A_L,A_{L+1},\ldots,A_R),\quad(B_L,B_{L+1},\ldots,B_R)$$

是一对好数组。

输入格式

第一行一个整数 TT。每组数据第一行一个整数 NN,第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N,第三行 NN 个整数 B1,…,BNB_1,\ldots,B_N。

输出格式

每组数据输出一行一个整数,表示合法区间的数量。答案不取模。

数据范围

1≤T≤1051\le T\le10^5,1≤N≤2×1051\le N\le2\times10^5,0≤Ai,Bi≤N0\le A_i,B_i\le N。所有测试用例的 NN 之和不超过 2×1052\times10^5。

样例 1

输入

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

输出

2
6
4